整除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;
}

评论