快速模幂运算

2019-04-13 17:16发布

站内文章 / 模拟电子
14918 0 1162
#include /* * 挑战程序设计竞赛 p122 */ __int64 mod_pow(__int64 x,__int64 n,__int64 mod){ //快速模幂运算 __int64 res = 1; while(n > 0){ if(n & 1){ //如果二进制位最低位为1，则乘上x^(2^i) res = (res * x) % mod; } x = (x * x) % mod; //将x平方 n >>= 1; //n右移一位，相当于n = [n / 2] 取下底 } return res; } bool is_prime(__int64 n){ //素数判定 for(int i = 2; i * i <= n; ++i){ if(!(n % i)) return false; } return n > 1; //排除负数,0,1的可能性 } __int64 n; void solve(){ bool flag = true; if(!is_prime(n)){ for(__int64 i = 1; i < n; ++i){ __int64 xn = mod_pow(i, n, n); __int64 x = i % n; if(xn != x){ flag = false; } } } else { flag = false; } if(flag){ printf("Yes "); } else { printf("No "); } } int main(){ while(scanf("%d", &n) != EOF){ solve(); } return 0; }

热门文章