Mathematics:Pseudoprime numbers(POJ 3641)

　　　　　　　　　　　　　　　　强伪素数

　　题目大意：利用费马定理找出强伪素数（就是本身是合数，但是满足费马定理的那些Carmichael Numbers）

　　很简单的一题，连费马小定理都不用要，不过就是要用暴力判断素数的方法先确定是不是素数，然后还有一个很重要的问题，那就是a和p是不互质的，不要用a^(p-1)=1(mod p)这个判据，比如4^6=4(mod 6)，但是4^5=4(mod 6)

 1 #include <iostream>
 2 #include <functional>
 3 #include <algorithm>
 4 
 5 using namespace std;
 6 typedef long long LONG_INT;
 7 
 8 LONG_INT witness(LONG_INT, LONG_INT, LONG_INT);
 9 bool Is_Prime(LONG_INT);
10 
11 int main(void)
12 {
13     LONG_INT coe, n;
14 
15     while (~scanf("%lld %lld", &n, &coe))
16     {
17         if (n == 0 && coe == 0)
18             break;
19         if (Is_Prime(n))
20             printf("no
");
21         else if (witness(coe, n, n) == coe)
22             printf("yes
");
23         else 
24             printf("no
");
25     }
26     return 0;
27 }
28 
29 bool Is_Prime(LONG_INT n)
30 {
31     for (int i = 2; i*i <= n; i++)
32     {
33         if (n%i == 0)
34             return false;
35     }
36     return true;
37 }
38 
39 LONG_INT witness(LONG_INT coe, LONG_INT level, LONG_INT n)
40 {
41     LONG_INT x, y;
42 
43     if (level == 0)
44         return 1;
45     x = witness(coe, level >> 1, n);
46 
47     if (x == 0)
48         return 0;
49     y = (x*x) % n;
50     if (level % 2 == 1)
51         y = (coe*y) % n;
52     return y;
53 }