南郵OJ 1079 111…

連結：http://acm.njupt.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=1079

題目：

111…

Time Limit(Common/Java):1000MS/3000MS          Memory Limit:65536KByte

Total Submit:301            Accepted:86

Description

給定任何不可被2或者5整除的整數n（0 <= n <= 10000）。有一些n的倍數，它們按十進制表示是一個由1組成的序列。那麼這種類型的n倍數中最小數有多少位？

Input

每行包含一個數n

Output

輸出位數。

注意：輸出部分的結尾要求包含一個多餘的空行。

Sample Input

3 

7 

9901

Sample Output

3

6

12

解題思路：

題目要求的是一個數t（t=1111......  && 0 == t % n）的位數，t = (10 * t) + 1;這是計算t的值得公式（從個位開始左移并且加1），每步都對n取餘，如果0 == t,說明n可以被t整除，此時的位數就是最小位數。

代碼：

#include <cstdio>

int main()
{
	int n;
	while(~scanf("%I64d", &n))
	{
		int t = 0, ans = 0;
		while(true)
		{
			t = (10 * t + 1) % n;
			ans++;
			if(0 == t) break;
		}
		printf("%d\n", ans);
	}
	return 0;
}