同和新媒体矩阵官网同和视频矩阵同和素材矩阵

登录 | 立即注册

同和创作矩阵 › ›博文归档› 技术博文归档 › 查看内容

21322_Pseudoprimenumbers

2022-5-16 18:19| 发布者: Hocassian| 查看: 42| 评论: 0|原作者: 肇庆学院ACM合集

摘要:

C:\Users\Administrator\Downloads\2019-10-12-10-14-4-89505149368899-Problem List-采集的数据-后羿采集器.html

Pro.ID

21322

Title

Pseudoprime numbers

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=21322

AC

17

Submit

47

Ratio

36.17%

时间&空间限制

Time Limit: 999/333 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

描述

Fermat's theorem states that for any prime number p and for any integer a > 1, a^p == 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 ≤ 1,000,000,000 and 1 < a < p, determine whether or not p is a base-a pseudoprime.

输入

Input contains several test cases followed by a line containing "0 0". Each test case consists of a line containing p and a.

输出

Description

Fermat's theorem states that for any prime number p and for any integer a > 1, a^p == 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 ≤ 1,000,000,000 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

Author

Gordon V. Cormack

样例输入

3 2
10 3
341 2
341 3
1105 2
1105 3
0 0

样例输出

no
no
yes
no
yes
yes

提示

Gordon V. Cormack

作者

最新评论

相关分类

返回顶部