首页 > 代码库 > HDU 1098 Ignatius's puzzle(数论-其它)
HDU 1098 Ignatius's puzzle(数论-其它)
Ignatius‘s puzzle
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".
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
Author
eddy
Recommend
We have carefully selected several similar problems for you: 1071 1014 1052 1097 1082
题目大意:
解题思路:给定一个k,找到最小的a 使得 f(x)=5*x^13+13*x^5+k*a*x ,f(x)%65永远等于0
因为 f(x+1)=5*(x+1)^13+13*(x+1)^5+k*a*x,所以 f(x+1)=f (x) + 5*( (13 1 ) x^12 ...... .....+(13 13) x^0 )+ 13*( (5 1 )x^4+...........+ ( 5 5 )x^0 )+k*a除了5*(13 13) x^0 、13*( 5 5 )x^0 和k*a三项以外,其余各项都能被65整除.那么也只要求出18+k*a能被65整除就可以了。
18+k*a=65*bax+by = c的方程有解的一个充要条件是:c%gcd(a, b) == 0
解题代码:“
#include <iostream> #include <cstdio> using namespace std; int gcd(int a,int b){ return b>0?gcd(b,a%b):a; } int main(){ int k; while(scanf("%d",&k)!=EOF){ if(18%gcd(k,65)==0){ for(int a=0;;a++){ if( (18+k*a)%65==0 ){ printf("%d\n",a); break; } } } else printf("no\n"); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。