poj 2551 Ones

Description

Given any integer 0 <= n <= 10000 not divisible by 2 or 5, some multiple of n is a number which in decimal notation is a sequence of 1's. How many digits are in the smallest such a multiple of n?

Input

Each line contains a number n.

Output

Output the number of digits.

Sample Input

3 
7 
9901

Sample Output

3
6
12

这是一道很有趣的水题~input中的数的某一倍数是全1的数字~要就计算出1的个数~

开始看到这道题时我的思路是将输入数字的倍数一个一个去验证~

发现不行~既耗时间~实现起来还麻烦~

后来就换了个思路~从1出发~从1到11到111~这样一个一个去计算是否是input的倍数~

但提交的时候一直是RE~后来看了DISCUSS之后发现~

每次只用计算余数~这样AC了~

下面是代码~

#include"stdio.h"

#include"stdlib.h"  

int main()
{
 int n;
 int s;
 int count;
 while(scanf("%d",&n)!=EOF)
 {
  s=1;
  count=1;
  s=s%n;
  while(s)
  {
   count++;
   s=s*10+1;  //位数上加1
   s%=n;   //求余数
  }
  printf("%d\n",count);
 }
}