「BZOJ3667」Rabin – Miller算法

2015年2月25日5,3173

Input

第一行：CAS,代表数据组数（不大于350），以下CAS行，每行一个数字，保证在64位长整形范围内，并且没有负数。你需要对于每个数字：第一，检验是否是质数，是质数就输出Prime
第二，如果不是质数，输出它最大的质因子是哪个。

Output

第一行CAS(CAS<=350，代表测试数据的组数)
以下CAS行：每行一个数字，保证是在64位长整形范围内的正数。
对于每组测试数据：输出Prime，代表它是质数，或者输出它最大的质因子，代表它是和数

Sample Input

6
2
13
134
8897
1234567654321
1000000000000

Sample Output

Prime
Prime
67
41
4649
5

HINT

数据范围：

保证cas<=350，保证所有数字均在64位长整形范围内。

题解

裸rho

卡常数丧心病狂

TAT

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#define ll long long 
#define inf 1000000000
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
ll gcd(ll a,ll b)
{
    return b==0?a:gcd(b,a%b);
}
int n;
ll x,mx;
vector<ll> q;
ll mul(ll a,ll b,ll p)
{
    ll tmp=(a*b-(ll)((long double)a/p*b+1e-8)*p);
    return tmp<0?tmp+p:tmp;
}
ll pow(ll a,ll b,ll p)
{
    ll ans=1;a%=p;
    for(ll i=b;i;i>>=1,a=mul(a,a,p))
        if(i&1)ans=mul(ans,a,p);
    return ans;
}
bool check(ll a,ll n,ll r,ll s)
{
    ll ans=pow(a,r,n),p=ans;
    for(int i=1;i<=s;i++)
    {
        ans=mul(ans,ans,n);
        if(ans==1&&p!=1&&p!=n-1)return 1;
        p=ans;
    }
    if(ans!=1)return 1;
    return 0;
}
bool MR(ll n)
{
    if(n<=1)return 0;
    if(n==2)return 1;
    if(n%2==0)return 0;
    ll r=n-1,s=0;
    while(r%2==0)r/=2,s++;
    for(int i=0;i<10;i++)
        if(check(rand()%(n-1)+1,n,r,s))
            return 0;
    return 1;
}
ll rho(ll n,ll c)
{
    ll k=2,x=rand()%n,y=x,p=1;
    for(ll i=1;p==1;i++)
    {
        x=(mul(x,x,n)+c)%n;
        p=y>x?y-x:x-y;
        p=gcd(n,p);
        if(i==k)y=x,k+=k;
    }
    return p;
}
void solve(ll n)
{
    if(n==1)return;
    if(MR(n)){mx=max(n,mx);return;}
    ll t=n;
    while(t==n)t=rho(n,rand()%(n-1)+1);
    solve(t);
    solve(n/t);
}
int main()
{
    n=read();
    while(n--)
    {
        x=read();
        mx=0;
        solve(x);
        if(mx==x)puts("Prime");
        else printf("%lld\n",mx);
    }
    return 0;
}

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<algorithm>

#include<vector>

#define ll long long

#define inf 1000000000

using namespace std;

ll read()

{

ll x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

ll gcd(ll a,ll b)

{

return b==0?a:gcd(b,a%b);

}

int n;

ll x,mx;

vector<ll> q;

ll mul(ll a,ll b,ll p)

{

ll tmp=(a*b-(ll)((long double)a/p*b+1e-8)*p);

return tmp<0?tmp+p:tmp;

}

ll pow(ll a,ll b,ll p)

{

ll ans=1;a%=p;

for(ll i=b;i;i>>=1,a=mul(a,a,p))

if(i&1)ans=mul(ans,a,p);

return ans;

}

bool check(ll a,ll n,ll r,ll s)

{

ll ans=pow(a,r,n),p=ans;

for(int i=1;i<=s;i++)

{

ans=mul(ans,ans,n);

if(ans==1&&p!=1&&p!=n-1)return 1;

p=ans;

}

if(ans!=1)return 1;

return 0;

}

bool MR(ll n)

{

if(n<=1)return 0;

if(n==2)return 1;

if(n%2==0)return 0;

ll r=n-1,s=0;

while(r%2==0)r/=2,s++;

for(int i=0;i<10;i++)

if(check(rand()%(n-1)+1,n,r,s))

return 0;

return 1;

}

ll rho(ll n,ll c)

{

ll k=2,x=rand()%n,y=x,p=1;

for(ll i=1;p==1;i++)

{

x=(mul(x,x,n)+c)%n;

p=y>x?y-x:x-y;

p=gcd(n,p);

if(i==k)y=x,k+=k;

}

return p;

}

void solve(ll n)

{

if(n==1)return;

if(MR(n)){mx=max(n,mx);return;}

ll t=n;

while(t==n)t=rho(n,rand()%(n-1)+1);

solve(t);

solve(n/t);

}

int main()

{

n=read();

while(n--)

{

x=read();

mx=0;

solve(x);

if(mx==x)puts("Prime");

else printf("%lld\n",mx);

}

return 0;

}

« 「codechef」February Lunchtime 2015

AwD

黄学长，这个rho没有跳出循环啊……陷入循环会炸的啊

kd35okc

黄学长泥的这个程序被我的同学随手卡掉了呀

hzwer

噢给个数据噜

hzwer.com _ Home | http://hzwer.com

「BZOJ3667」Rabin – Miller算法

Input

Output

Sample Input

Sample Output

HINT

题解

分类目录

热门文章

Myfriends

近期评论