HDU1098
证明是看大牛的...自己好好理解吧做这道题应该拿出高中那种做选择题的技巧出来。任意x都满足 65|f(x) ,那么f(1)一定在列,f(1)=18+ka , 那么必须满足 65|(18+ka) ,
从0–64遍历 a 即可,当然这只是必要条件,至于充分条件那得靠人品了,我不想误导别人,下面给出证明。
采用归纳假设法,f(x)=5*x^13+13*x^5+k*a*x 。
先假设 65|f(x) 成立 ,要证明对于任意x都成立,那么只需证明 65|f(x+1) 成立。
f(x+1)=5*(x+1)^13+13*(x+1)^5+k*a*(x+1) ;
用二项式定理展开f(x+1)=5*( C(13,0)+C(13,1)*x+……+C(13,13)*x^13 ) + 13*( C(5,0)+C(5,1)*x+……+C5,5)*x^5 ) + k*a*(x+1)
可以得到 f(x+1)=f(x)+5*( C(13,0)+C(13,1)*x+……+C(13,12)*x^12 ) + 13*( C(5,0)+C(5,1)*x+……+C5,4)*x^4 ) + k*a
f(x+1)=f(x)+ 5*( C(13,1)*x+……+C(13,12)*x^12 ) + 13*( C(5,1)*x+……+C(5,4)*x^4 ) + 5*C(13,0)+13*C(5,0)+ k*a
显然f(x)+ 5*( C(13,1)*x+……+C(13,12)*x^12 ) + 13*( C(5,1)*x+……+C5,4)*x^4 ) 能被65整除,那么只需满足后部分被65整除即可。
5*C(13,0)+13*C(5,0)+ k*a =18+k*a ;
只要满足65|(18+k*a),65|f(x+1)就成立,也就是f(x)对于任意x都满足 65|f(x) 。
对于给定的k,只有搜索满足 65|(18+k*a) 的a 即可,a的大小一定是1—-64。
代码:
#include<iostream>
using namespace std;
int main(){
int a;
while(cin>>a){
a %= 65;
int flag=0;
for(int i=1;i<=65;i++){
if(i*a%65==47){ cout<<i<<endl; flag=1; break; }
}
if(!flag) cout<<"no"<<endl;
}
}
补充:软件开发 , C++ ,