自己做的网站怎样对接支付宝,建设网站的语言,开发者选项怎么设置最流畅,武威百度做网站多少钱原本是想把这个算法搞懂的#xff0c;然后在网上看了又看#xff0c;觉得#xff0c;还是有时间再来看吧#xff0c;我错了。
看到了一个大佬的博客#xff0c;顺带收集一下板子
这个板子可以求大数的最大的因子。
#define LL long long
bool IsPrime(LL);//返回素性测…原本是想把这个算法搞懂的然后在网上看了又看觉得还是有时间再来看吧我错了。
看到了一个大佬的博客顺带收集一下板子
这个板子可以求大数的最大的因子。
#define LL long long
bool IsPrime(LL);//返回素性测试结果
LL GCD(LL,LL);//返回两个数的GCD
LL Mix(LL,LL,LL);//返回两个数在模运算下的乘积void MaxFactor(LL n,LL ans)
{if(n1||nans||IsPrime(n)){return;//判断特殊情况n为1或素数}for(LL crand()%(n-1)1;;c){//为防止随机数无效化使用死循环LL t1rand()%(n-1)1,t2(Mix(t1,t1,n)c)%n;LL p1,i0,g0;while(t1!t2){pMix(p,abs(t1-t2),n);if(!p){//乘积为0时说明找到了一个因子gGCD(n,abs(t1-t2));if(g1gn){MaxFactor(g,ans);MaxFactor(n/g,ans);}return;}i;if(i127){//当有127个数时强制测试gGCD(n,p);if(g1gn){MaxFactor(g,ans);MaxFactor(n/g,ans);return;}p1,i0;}t1(Mix(t1,t1,n)c)%n;t2(Mix(t2,t2,n)c)%n;t2(Mix(t2,t2,n)c)%n;}gGCD(n,p);if(g1gn){//循环退出后收尾MaxFactor(g,ans);MaxFactor(n/g,ans);return;}}
}又找了一个板子这个好像可以求出所有的因子保存在数组factor中
#includeiostream
#includecmath
#includecstring
#includealgorithm
#includecstdio
#includestdlib.h
#includetime.h
#define times 20
using namespace std;
#define ll long long
ll total;
ll factor[110];
ll qmul(ll a,ll b,ll M){a%M;b%M;ll ans0;while (b){if (b1){ans(ansa)%M;}a(a1)%M;b1;}return ans%M;
}///快乘因为两个longlong的数相乘可能会溢出所以这里转乘法为加法思想和快速幂相似
ll qpow(ll a,ll b,ll int M){ll ans1;ll ka;while(b){if(b1)ansqmul(ans,k,M)%M;kqmul(k,k,M)%M;b1;}return ans%M;
}
bool witness(ll a,ll n,ll x,ll sum){ll judgeqpow(a,x,n);if (judgen-1||judge1)return 1;while (sum--){judgeqmul(judge,judge,n);if (judgen-1)return 1;}return 0;
}
bool miller(ll n){ ///判断素数if (n2)return 0;if (n2)return 1;if ((n1)0)return 0;ll xn-1;ll sum0;while (x%20){x1;sum;}for (ll i1;itimes;i){ll arand()%(n-1)1;if (!witness(a,n,x,sum))return 0; ///费马小定理的随机数检验}return 1;
}
ll gcd(ll a,ll b){return b0?a:gcd(b,a%b);
}
ll pollard(ll n,ll c){ll x,y,d,i1,k2;xrand()%n;yx;while (1){i;x(qmul(x,x,n)c)%n; ///不断调整xdgcd(y-x,n);if (d0)d-d;if (d1dn)return d; ///找到因子if (yx)return n; ///找到循环返回n重新来if (ik){ ///一个优化yx;k1;}}
}
void find(ll n){///寻找这个数的素因子并存起来if (miller(n)){factor[total]n;return ;}ll pn;while (pn) ppollard(p,rand()%(n-1)1); ///不断找因子知道找到为止返回n说明没找到find(n/p);find(p);
}
int main(){ll n,m,i,t;scanf(%lld,t);while (t--){scanf(%lld,n);if (miller(n)) printf(Prime\n);else {memset(factor,0,sizeof(factor));total0;find(n);sort(factor1,factortotal1);printf(%lld\n,factor[1]);}}
}
