爆0求助,求神牛们指点迷津
查看原帖
爆0求助,求神牛们指点迷津
1299348
RockyQ012楼主2024/5/14 21:05

做过一道类似的题样例过了但爆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;
}
2024/5/14 21:05
加载中...