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; }