POJ 3641: Psudoprime numbers, POJ 1995 : Raising Modulo Numbers

解法

繰り返し二乗をやるだけ．

POJ 3641

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

ll p, a;
int main(){
    for(;;){
        scanf("%lld%lld", &p, &a);
        if(p == 0 && a == 0) return 0;
        ll q = 1, s = a;
        for(int t = p; t > 0; t >>= 1){
            if(t & 1) q = (q * s) % p;
            s = (s * s) % p;
        }
        printf("%s\n", !isPrime(p) && a == q ? "yes": "no");
    }
}

POJ 1995

ll mod_pow(ll a, ll n, ll M){
    if(n == 0) return 1;
    ll p = mod_pow((a * a) % M, n / 2, M);
    return (p * (n & 1 ? a: 1)) % M;
}

int Z, H;
ll M, A[45010], B[45010];
int main(){
    scanf("%d", &Z);
    for(; Z > 0; --Z){
        scanf("%lld%d", &M, &H);
        for(int i = 0; i < H; ++i)
            scanf("%lld%lld", &A[i], &B[i]);
        ll res = 0;
        for(int i = 0; i < H; ++i){
            res = (res + mod_pow(A[i], B[i], M)) % M;
        }
        printf("%lld\n", res);
    }
    return 0;
}