posts - 210, comments - 61, trackbacks - 0, articles - 0
   :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

关于数论中的同余

Posted on 2007-02-06 01:43 魔のkyo 阅读(390) 评论(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)
只有注册用户登录后才能发表评论。