题解报告:hdu 1098 Ignatius's puzzle

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1098

题目中文是这样的:

  伊格内修斯在数学上很差,他遇到了一个难题,所以他别无选择,只能上诉埃迪。 这个问题描述:f(x)= 5 * x ^ 13 + 13 * x ^ 5 + k * a * x,输入一个非正整数k(k <10000),找到最小非负整数a, 使得任意的整数x,65 | f(x)如果不存在那个a,就打印“否”。

输入

  输入包含多个测试用例。 每个测试用例由非负整数k组成,样例输入中有更多详细信息。  

输出

  输出包含一个字符串“no”,如果找不到a,或者您应该输出一行包含示例输出中的a.More详细信息。

解题思路:题目的意思就是:给定f(x)=5*x^13+13*x^5+k*a*x,现给出非负整数k ,求取任意x都能使f(x)%65==0成立的最小非负整数a。这道题采用数学归纳法:当x=0时,f(0)=0能够被65整除,即0/65==0,假设f(x)%65==0,则只需证明f(x+1)%65==0,即对于任意的整数x都成立。

下面证明f(x+1)%65==0成立:

 因为f(0)=0 能被65整除, 假设(f(1)=18+ka)%65==0,当f(x)能整除65,那么f(x+1)=f(x)+5*[C(13,1)x^12+……+C(13,13)x^0]+13*[C(5,1)x^4……+C(5,5)x^0]+ka=f(x)+5*[C(13,1)x^12+……+C(13,12)x^1]+13*[C(5,1)x^4……+C(5,4)x^1]+18+ka。(二项式展开式)可以发现除(18+ka)这项之外,其他的都能被65整除,所以要使f(x+1)%65==0这个等式成立,只需满足(18+ka)%65==0即可(这是一个必要不充分条件)。

好了,现在问题转化为求(18+ka)%65的那个最小非负整数a,因为k最小取1,即k=1时,a最大能取到65,所以只需枚举a到65即可,若a大于65则输出"no"。

这里证明为什么a只需枚举到65:第一点:当k%65==0时,18+k*a是永远除不尽65的,第二点:k%65!=0时,那么a就从1开始枚举,不断地尝试18+k*a是否能除尽65,找到即止。当a==65,也就是已经找了一个周期了,再找下去也找不到适当的a了,所以a只需枚举到65即可。

AC代码:

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int main()
 4 {
 5     int k,a;
 6     while(cin>>k){
 7         for(a=1;a<=65;a++)
 8             if((18+k*a)%65==0){cout<<a<<endl;break;}
 9         if(a>65)cout<<"no"<<endl;
10     }
11     return 0;
12 }
原文地址:https://www.cnblogs.com/acgoto/p/8687849.html