首页 > 代码库 > hdu1098:Ignatius's puzzle
hdu1098:Ignatius's puzzle
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1098
参考链接:http://blog.csdn.net/baidu_23955875/article/details/42581983
费马小定理?!
看了参考链接中对费马小定理的解释后茅塞顿开
详细解释参见代码
代码:
1 /** 2 *费马小定理 :假如p是质数,且Gcd(a,p)=1,那么 a^(p-1) ≡1(mod p)。 3 *即:假如a是整数,p是质数,且a,p互质(即两者只有一个公约数1), 4 *那么a的(p-1)次方除以p的余数恒等于1。该定理是1636年皮埃尔·德·费马发现的。 5 */ 6 7 /** 8 *f(x)=5x^13+13x^5+kax 9 *设g(x)=f(x)/x/65 即g(x)=x^12/13+x^4/5+ka 10 *由费马小定理,g(x)实际上转化为g(x)=(13+5)/65+ka/65 11 *故枚举a即可 12 *而a>65之后实际上进入下一周期,故只需枚举到65 13 */ 14 15 int main() { 16 int k; 17 while (~scanf("%d", &k)) { 18 int i; 19 for (i = 1; i <= 65; i++) { 20 if ((18 + k*i) % 65 == 0) { 21 cout << i << endl; 22 break; 23 } 24 } 25 if (i > 65) { 26 cout << "no" << endl; 27 } 28 } 29 return 0; 30 }
hdu1098:Ignatius's puzzle
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。