Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 6053 | Accepted: 2423 |
Description
Fermat's theorem states that for any prime number p and for any integer a > 1, ap = a (mod p). That is, if we raise a to the pth power and divide by p, the remainder is a. Some (but not very many) non-prime values of p, known as base-a pseudoprimes, have this property for some a. (And some, known as Carmichael Numbers, are base-a pseudoprimes for all a.)
Given 2 < p ≤ 1000000000 and 1 < a < p, determine whether or not p is a base-a pseudoprime.
Input
Input contains several test cases followed by a line containing "0 0". Each test case consists of a line containing p and a.
Output
For each test case, output "yes" if p is a base-a pseudoprime; otherwise output "no".
Sample Input
3 2 10 3 341 2 341 3 1105 2 1105 3 0 0
Sample Output
no no yes no yes yes
题意:
输入两个数p(2 ~ 1000000000),a (1 ~ p)。如果p是素数则输出no,如果不是,则判断 a ^ p % p 是否等于 a,若是则输出yes,不是则输出no。
思路:
快速幂。其时间复杂度是 O(log₂N), 与朴素的O(N)相比效率有了极大的提高。但是要变成边模,以免爆long long。
AC:
#include <stdio.h> #include <string.h> typedef long long ll; int pri(int a) { for(int i = 2;i * i <= a;i++) if(!(a % i)) return 0; return 1; } int mod_pow(ll x,ll n,ll mod) { ll ans = x,res = 1; while(n) { if(n & 1) res = res * x % mod; x = x * x % mod; n >>= 1; } return (res == ans ? 1 : 0); } int main() { int a,p; while(~scanf("%d%d",&p,&a) && (a + p)) { if(!pri(p) && mod_pow(a,p,p)) puts("yes"); else puts("no"); } return 0; }
相关推荐
美国新数学丛书 英文版 第一册 (NML-01)Numbers: Rational and Irrational by Ivan Niven 有理数和无理数
Prime Numbers - The Most Mysterious Figures in Math
北大POJ3292-Semi-prime H-numbers 解题报告+AC代码
numbers.js 是一个客户端 javascript 库,它向标准 Math 库添加了一些高级数学功能。 图书馆内容 README.md:这个文件。 numbers-xyzjs:数字库的xyz版本,适合开发。 numbers-xyz-min.js:数字库的xyz版本,适用...
北大POJ2739-Sum of Consecutive Prime Numbers 解题报告+AC代码
The ancient Greeks discovered them, but it wasn't until the nineteenth century that irrational numbers were properly understood and rigorously defined, and even today not all their mysteries have been...
欧拉公式中的数学美,在欧拉公式中蕴含着数学美, 应在教学教育中开谬戮学美学基才鲜数学美欣甲课程
Random Numbers with Android studio.
Numbers 是专为移动设备设计的极富创意的电子表格应用程序。完全针对 iPad、iPhone 和 iPod touch 构建,它可让您仅用手指就可以在几分钟内制作出带有表格、图表、照片和图形的吸引人的电子表格。有超过 250 种易于...
Numbers - 函數列表 - Apple (台灣).pdf ,使用mac 的excel 快速查閱 資源
This is a book about numbers and how those numbers are represented in and operated on by computers. It is crucial that developers understand this area because the numerical operations allowed by ...
前端项目-numbers.js,Advanced Mathematics Library for JavaScript
北大POJ3252-Round Numbers 解题报告+AC代码
个人预算.numbers
Businesses like to have memorable telephone numbers. One way to make a telephone number memorable is to have it spell a memorable word or phrase. For example, you can call the University of Waterloo ...
姓名+手机号.numbers
整合了 line-numbers 实现行号显示。 <link rel="stylesheet" type="text/css" href="line-numbers.css"> <script src="highlight.min.js"></script> <script src="highlightjs-line-numbers.js"/>...
You are given two non-empty linked lists representing two non-negative integers....You may assume the two numbers do not contain any leading zero, except the number 0 itself. java AC版本
油耗计算.numbers
Numbers函数大全,方便实用,Mac可以告别excel。Numbers函数大全,方便实用,Mac可以告别excel。