poj-3641

//712K  0MS G++
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;

long long a, p;

// long long power2(long long a, long long n)
// {
//     long long ret = 1;
//     for (long long m = a; n > 0; n >>= 1, m = m * m % p)
//         if (n & 1)
//             set = ret * m % p;
//     return ret;
// }

long long power(long long a, long long n) {
    if (n == 1) {
        return a%p;
    }
    long long  additional = 1;
    long long subRes = power(a, n/2);
    long long res = (subRes*subRes)%p;
    if (n & 1) {
        res = (res*a)%p;
    }
    return res;
}


bool prime(int a)
{
    for (int i = 2; i * i <= a; i++)
        if (a % i == 0)
            return false;
    return true;
}

int main()
{
    //freopen("t.txt", "r", stdin);
    while (scanf("%lld%lld", &p, &a), a | p)
    {
        long long x = power(a, p);
        // long long x2 = power2(a, p);
        // printf("COMPARE %lld %lld\n", x, x2);
        if (x == a && !prime(p))
            printf("yes\n");
        else
            printf("no\n");
    }
    return 0;
}

利用了次方的模运算来对大数进行压缩：

模运算满足分配率，（a*b）mod n = ((a mod n)*(b mod n)) mod n

那么对于N的x次方%M，

则可以不断的将N/2向下递归分解， power()是递归， power2()用的是循环（超别人的, 不是很清楚循环的写法），

注意的是，因为数值太大，因此任何两个大数相乘都要取模，在power函数中，一开始res = subRes*subRes时没有%p，造成了WA，

因此只要有两个大数乘，就都要再接着取一次模。

还是搞不清楚power的 递归 转 循环的写法，MARK下.