HDU1098数学归纳

Ignatius’s puzzle

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 10129 Accepted Submission(s): 7108

Problem Description Ignatius is poor at math,he falls across a puzzle problem,so he has no choice but to appeal to Eddy. this problem describes that:f(x)=5*x^13+13*x^5+k*a*x,input a nonegative integer k(k<10000),to find the minimal nonegative integer a,make the arbitrary integer x ,65|f(x)if no exists that a,then print “no”.

Input The input contains several test cases. Each test case consists of a nonegative integer k, More details in the Sample Input.

Output The output contains a string “no”,if you can’t find a,or you should output a line contains the a.More details in the Sample Output.

Sample Input 11 100 9999

Sample Output 22 no 43

---

思路

1、先把题目含义给搞明白：给定一个方程式f(x)=5*x^13+13*x^5+k*a*x，给定一个非负整数k，求能不能找到一个尽量小的非负整数a，使得上述方程式中的x任意取值，结果都能被65整除，如果有，输出a的值，否则输出no

2、看到这种数学题目，一般可以带数据来实现证明，当x=0时f(x)=0，而0e==0是可以的，f(x+1)=f(x)+18+k*a.(这个可以提取5*x^13+13*x^5+k*a*x)，因为f(0)可以被65整除，所以f(1)要被65整除的话，需要18+k*a被65整除。所以事情变的简单，只要证明18+k*a被65整除即可

3、根据思路我就开始写了，然后写到a的范围时，卡住了，不知道a应该要被限制为多大，然后我就随便写了个10000（不会超时），也被AC了。后来我又想了下随便找个数也不是办法，不如打表找找a是不是有规律或者大概都在什么范围，我就打表，发现最大值是64，所以就改了65，AC了。不过这个a的最应该求的方法是：（看了网上的）

因为，当a==66时 也就相当于已经找了一个周期了，所以再找下去也找不到适当的a了 (18+k*a)e=(18e+k*ae)e; 当a=66时k*66e==ke(即a=1时)

打表程序+结果

---

代码

#include <iostream> #include <stdio.h> using namespace std; int main() { int k; while(cin>>k) { int count=0; int a; for(a=0;a<65;a++) { if((18+k*a)%65==0) { count++; break; } } if(count==0) { cout<<"no"<<endl; } else{ cout<<a<<endl; } } return 0; }