整除65的多项式 Time Limit:1s Memory Limit:1000k Total Submit:1749 Accepted:1157 下载样例程序(PE) -------------------------------------------------------------------------------- Problem f(x)=5*x^13+13x^5+kax. 输入非负整数k, (k<10000) 找到最小的正整数a,使得对于任意整数x, 65|f(x) 若不存在这样的a,输出 "no" (无引号) Input 有多组输入，每行一个k. Output 每行输出一个a Sample Input 9 Sample Output 63 Source fairfox 　　我喜欢这道题，因为它的数学性质重一些，我在纸上算了半天，结果编了一小段程序搞定，虽然很简单我还是把我的推导过程写一下。 　　用到的数学知识就是初等数论吧，虽然我还没学，就我所了解的（初中的时候数学竞赛有介绍同余理论）做了一些推理得出的。 　　首先观察出65=5*13，５和13都是素因数，假设f(x)被65整除，那么f(x)一定能被5整除，因为f(x)=5*x^13+13x^5+kax，所以马上得到，一定满足13x^5+kax被5整除，同样的道理可以得到5x^13+kax一定要被13整除。我引这样一种记法，如果一个数n被数m除余r的话，即n%m==r，那么记为n≡r(mod m)。 　　这样的式子称为同余式，同余式跟等式在运算上非常的相似，有如下一些运算定律： 如果 　　n1≡r1(mod m) 　　n2≡r2(mod m) 那么 　　n1+n2≡r1+r2(mod m) 　　n1*n2≡r1*r2(mod m) 　　n1^k≡r1^k(mod m) [k=0,1,2...] 这就是一把刀，下面操刀解题。 继续前面的过程： 　　现在我们有，如果f(x)能被65整除，那么一定有： 　　13x^5+kax≡0(mod 5) 　　5x^13+kax≡0(mod 13) 　　以13x^5+kax≡0(mod 5)为例，可以写成x(13x^4+ka)≡0(mod 5)，下面按同余的运算定律对x进行分类，x为任意整数，对于模(mod)为5来说可以分5类，即按余数为0,1,2,3,4分成5类，第k类可以写成{x|x≡k(mod 5)}，这一类数在余数运算中意义是完全一样的，再由前面的运算律马上得到： 　　3x^4+ka≡0(mod 5) 当x为第k类时，k≠0，因为如果x能被5整除，上式直接满足 　　所以只要把x=1,2,3,4代入，算出x^4≡1(mod 5)，这里我猜想这样的定理，是否对于任意的n都满足，对于任意的正整数x，x^(n-1)≡1(mod n)，我用了少量几个数用计算器算出来是成立的，但还需要数学上的证明。 　　所以有3+ka≡0(mod 5)，即ka≡2(mod 5)。 　　同样的道理同样的过程还可以得到：ka≡8(mod 13)这两式联立得到一个方程，方程中不是'='而是同余号，不妨这样设，由下式可设ka=13m+8，由上式可以又写成同余式，得：13m+8≡2(mod 5) 　　所以 　　3m≡4(mod 5) [因为13≡3(mod 5)] 　　将m按模为5分5类，每一类代入方程，得到m≡3的这一类满足方程，且唯一满足方程，所以解出来m≡3(mod 5)，即m=5n+3，代入ka=13m+8得 　　ka=13(5n+3)+8=65n+47 　　写成同余式即 　　ka≡47(mod 65) 　　这是终级式，砍杀了半天就砍出这么个小样，挺简单的。既然模是65，对于求最小的正整数a，a只有在1到65中取值，一个循环判断搞定。补充一点，k输入范围是k<10000，如果相乘可能超出int型整数范围，其实k再取多大都一点用没有，终级式是按65分类，我们对输入的k，打个折，除65取余，结果都是一样的。 Ｃ＋＋： #include<iostream> using namespace std; int main() {     int k,a;     while(cin>>k)     {         k%=65;         for(a=1;a<=65;++a)         {             if(k*a%65==47)break;         }         if(a>65)cout<<"no"<<endl;         else cout<<a<<endl;     }     return 0; }

评论