做过一道类似的题样例过了但爆0了
费马小定理:如果p是一个素数,对于任何a > 1有a的p次方模p等于a也就是说如果把a扩大到它的p次方,然后再除以p,余数应该是a。 但有些数字p,它们不是质数,但对于一些特殊的a,它仍然满足上述性质,我们称这样的p叫"伪质数" 判断p是否是一个伪质数
样例输入
3 2
10 3
341 2
341 3
1105 2
1105 3
0 0
样例输出 no no yes no yes yes
#include <bits/stdc++.h>
using namespace std;
int qpow(int p , int a) {
int ans = 1;
int mod = p;
while(p) {
if(p & 1) ans = ans * a % mod;
a = a * a % mod;
p = p >> 1;
}
return ans;
}
int pdzs(int p){
int f = 0;
for(int i = 2 ; i < p ; ++i){
if(p % i == 0){
f = 1;
break;
}
}
if(f == 1)return true;
else return false;
}
int main() {
while(1){
int p , a;
cin >> p >> a;
if(p == 0 && a == 0) return 0;
else if (a <= 1 || a >= p) {
cout << "no" << endl;
continue;
}
else if(qpow(p , a) == a && pdzs(p)) cout << "yes" << endl;
else cout << "no" << endl;
}
return 0;
}