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?
Sample input
3
7
9901
Output for sample input
3
6
12
可以不用高精度除法，直接如下，很巧妙，不通用。
#include <stdio.h>
int main()
{
int n, a, b;
while (EOF != scanf("%d", &n))
{
a = 1;
b = 1;
while (a)
{
a = (a * 10 + 1) % n;
++b;
}
printf("%d\n", b);
}
}
高精度除法
----
#include<iostream>
#include<cstdlib>
using namespace std;
int a[9]={1,11,111,1111,11111,111111,1111111,11111111,111111111};
const int MOD=11111;
bool test(int i,int j)
{
if(j<10)
{
if(a[j-1]%i==0)
return true;
return false;
}
else
{
int temp=0;
int k=j%5;
int p=j/5;
if(k==0)
{
for(int m=1;m<=p;m++)
{
temp*=100000;
temp+=MOD;
temp%=i;
}
if(temp==0)
return true;
else
return false;
}
else
{
int m,f=1;
for(m=1;m<=p;m++)
{
temp*=100000;//由于5位5位除，應當乘上10^5;
temp+=MOD;
temp%=i;
}
for(m=0;m<k;m++)//最后應當乘以其后的位數乘10^n，
f*=10;
if((temp*f+a[k-1])%i==0)
return true;
else
return false;
}
}
}
int main()
{
//freopen("s.txt","r",stdin);
//freopen("key.txt","w",stdout);
int i;
while(cin>>i)
{
if(i==1)
{
cout<<'1'<<endl;
continue;
}
for(int j=2;;j++)
{
if(test(i,j))
{
cout<<j<<endl;
break;
}
}
}
//system("PAUSE");
return 0;
}
posted on 2009-07-18 17:38
luis 閱讀(1253)
評論(0) 編輯 收藏 引用 所屬分類:
給我啟發題