暴力枚举+判断
一般数的原根都不会太大,所以暴力枚举能跑出来。
原根有一个性质: \(g^k\equiv 1 \pmod P\) 当且仅当 \(k=P-1\) 时成立(\(P\) 是质数)
#include<bits/stdc++.h>
using namespace std;
#define rint register int
int cnt,fac[1000010];
const int P=1004423491;
void getfac(int x) {
for(rint i=2,mx=sqrt(x);i<=mx;++i) {
if(x%i==0) {
fac[++cnt]=i;
while(x%i==0)x/=i;
}
}
}
int qpow(int n,int k) {
int res=1;
while(k) {
if(k&1)res=1ll*res*n%P;
n=1ll*n*n%P;
k>>=1;
}
return res;
}
bool check(int x) {
for(rint i=1;i<=cnt;++i) {
if(qpow(x,(P-1)/fac[i])==1)return 0;
}
return 1;
}
int main() {
getfac(P-1);
for(rint i=2;i<P;++i) {
if(check(i)) {
printf("%d\n",i);
return 0;
}
}
}
原文链接: https://www.cnblogs.com/zzctommy/p/12537369.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/194675
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!