uva 10127: Ones

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?

例如,当n=3时,我们发现3*37=111。而111有3个1,所以输出3。

当n=7时,我们发现7*15873=111111,而111111有6个1,所以输出6。

这个问题,最直观的暴力做法是,把n的所有倍数都拿来从小到大试一遍。如果发现某个数的每一位都是1,那么就停。但是这么做会算术溢出。

如果我们把问题倒过来,从1、11、111开始,挨个看它们是不是n的倍数,问题就简单多了。

令a(0) = 1 , a(i) = a(i-1)*10 +1

那么a(1)=11, a(2)=111, a(3)=1111 ,....

另 b(i) = a(i) % n = (a(i-1)10 +1) % n = (a(i-1)%n 10 + 1) % n

则b(i) = (b(i-1) * 10 +1) % n

所以有0<= b(i) < n 。这样就没有算术溢出的问题了。

代码如下:

int resolve(int n){
  if(n==1) return 1;
  int ret=2;
  for(int i=11;i%n;ret++) i=(i*10+1)%n;
  return ret;
}

此博客中的热门博文

在windows下使用llvm+clang

少写代码,多读别人写的代码

tensorflow distributed runtime初窥