Posted on 2007-02-06 01:43
魔のkyo 阅读(484)
评论(0) 编辑 收藏 引用 所属分类:
Programming
题目的大概意思是
给出一个整数N ，0<=N<=10000,N既不是2的倍数又不是5的倍数，求一整数S，S既是N的倍数，且S的每一位都是1(在十进制的意义下)。输出S的数位。
题目很简单，按照题目意思写出来如下代码：
int main()
{
int n;
while(scanf("%d",&n)!=EOF){
int x=1;
int i=1;
while(x%n){
x=(x*10+1);
i++;
}
printf("%d\n",i);
}
}
但是sample都过不了，因为sample中就有一个输出是12，显然int不够长，然后我问了金XX，金告诉我不要大整数，大概10分钟后我又问了一次……，然后他告诉我用到了“同余”，其实我本来也不是不知道，但是没想到可以这样用，也许第一次碰到这样的题目，看了数论的书，
“a,b关于模m同余”是等价关系，记作a=b(mod m)
若a1=a2(mod m),且b1=b2(mod m)，则a1+b1=a2+b2(mod m)
若a1=a2(mod m),且b1=b2(mod m)，则a1*b1=a2*b2(mod m)
回到题目x%n==0就是x=0(mod n)
若x'=x(mod n),且10=10(mod n)，且1=1(mod n)，则x'*10+1=x*10+1(mod n)
因此，不妨将x(mod n)记做x，这样就可以避免超过int的范围了
//
2007-02-06 00:48:10 Accepted 1889 C++ 00:00.00 832K
//
数论的同余
//
以后看到整除要想到同余，太有用了，见数论笔记
#include
<
iostream
>
using
namespace
std;
int
main()
{
int
n;
while
(scanf(
"
%d
"
,
&
n)
!=
EOF){
int
x
=
1
;
int
i
=
1
;
while
(x
%
n){//这里将%n去掉也可以，但是为了和上面的code对比，我还是保留着
x
=
(x
*
10
+
1
)
%
n;
i
++
;
}
printf(
"
%d\n
"
,i);
}
}
再总结一下，若x'=x(mod n),则f(x')=f(x)(mod n),其中f表示
整数域上的多项式整系数多项式(编辑:2011-06-24)