P4714 「数学」约数个数和

题解:

会了Miller-Rabin这题就很简单了

首先这种题很容易想到质因数分解

但是暴力根号算法是不行的

所以要用到

Miller-Rabin素数

https://blog.csdn.net/ltyqljhwcm/article/details/53045840

对于要判断的数n

1.先判断是不是2,是的话就返回true。

2.判断是不是小于2的,或合数,是的话就返回false。

3.令n-1=u*2^t,求出u,t,其中u是奇数。

4.随机取一个a,且1<a<n

/*根据费马小定理,如果a^(n-1)≡1(mod p)那么n就极有可能是素数,如果等式不成立,那肯定不是素数了

因为n-1=u*2^t,所以a^(n-1)=a^(u*2^t)=(a^u)^(2^t)。*/

5.所以我们令x=(a^u)%n

6.然后是t次循环,每次循环都让y=(x*x)%n,x=y,这样t次循环之后x=a^(u*2^t)=a^(n-1)了

7.因为循环的时候y=(x*x)%n,且x肯定是小于n的,正好可以用二次探测定理,

如果(x^2)%n==1,也就是y等于1的时候,假如n是素数,那么x==1||x==n-1,如果x!=1&&x!=n-1,那么n肯定不是素数了,返回false。

8.运行到这里的时候x=a^(n-1),根据费马小定理,x!=1的话,肯定不是素数了,返回false

9.因为Miller-Rabin得到的结果的正确率为 75%,所以要多次循环步骤4~8来提高正确率

10.循环多次之后还没返回,那么n肯定是素数了,返回true

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int kk=;
ll n;
ll C(ll x,ll y)
{
if (y==) return(x);
if (y%==) return(((C(x,y/)*)%n+x)%n);
else return((C(x,y/)*)%n);
}
ll M(ll x,ll y)
{
if (y==) return(x);
ll tmp=M(x,y/);
if (y%==) return(C(C(tmp,tmp),x));
else return(C(tmp,tmp));
}
bool pd()
{
if (n==) return ;
if (n<) return ;
ll m=n-;
int k=;
while (!(m&))
{
k++; m>>=;
}
for (int i=;i<=kk;i++)
{
ll x1=rand()%(n-)+;
ll x2=M(x1,m);
ll y=;
for (int j=;j<=k;j++)
{
y=C(x2,x2);
if (y==&&x2!=&&x2!=n-) return ;
x2=y;
}
if (y!=) return ;
}
return ;
}
int main()
{
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
while (cin>>n)
{ if (pd()) cout<<"T"; else cout<<"F";
cout<<endl;
}
return ;
}

Pollard-rho算法:

上一篇:两种常用的启动和关闭MySQL服务


下一篇:linux 系统监控系列之vmstat