首页 > 代码库 > hdoj 1089(费马小定理)

hdoj 1089(费马小定理)

题目大意:方程f(x)=5*x^13+13*x^5+k*a*x;输入任意一个数k,是否存在一个数a,对任意x都能使得f(x)能被65整出。现假设存在这个数a ,因为对于任意x方程都成立所以,当x=1时f(x)=18+ka又因为f(x)能被65整出,故设n为整数可得,f(x)=n*65;即:18+ka=n*65;因为n为整数,若要方程成立则问题转化为,对于给定范围的a只需要验证,是否存在一个a使得(18+k*a)%65==0所以容易解得注意,这里有童鞋不理解为毛a只需到65即可因为,当a==66时也就相当于已经找了一个周期了,所以再找下去也找不到适当的a了如果你非要证明的话,可以利用了取模过程与数的运算的次序上可交换原理简单证明一下本身看看就知道,这里就不证了。。


代码:

#include<stdio.h>

int main()
{
 int k,i,flag;
 while(scanf("%d",&k)!=EOF)
 {
  flag=1;
        for(i=1;i<65;i++)
  {
   if((18+i*k)%65==0)
   {
    printf("%d\n",i);
    flag=0;
    break;
   }
  }
  if(flag) printf("no\n");
   
 }
 return 0;
}