首页 > 代码库 > [HDU 4344]Mark the Rope(Pollard_rho+Miller_Rabin)

[HDU 4344]Mark the Rope(Pollard_rho+Miller_Rabin)

Description

Eric has a long rope whose length is N, now he wants to mark on the rope with different colors. The way he marks the rope is:
1. He will choose a color that hasn’t been used
2. He will choose a length L (N>L>1) and he defines the mark’s value equals L
3. From the head of the rope, after every L length, he marks on the rope (you can assume the mark’s length is 0 )
4. When he chooses the length L in step 2, he has made sure that if he marks with this length, the last mark will be at the tail of the rope
Eric is a curious boy, he want to choose K kinds of marks. Every two of the marks’ value are coprime(gcd(l1,l2)=1). Now Eric wants to know the max K. After he chooses the max K kinds of marks, he wants to know the max sum of these K kinds of marks’ values.
You can assume that Eric always can find at least one kind of length to mark on the rope.

Solution

质因数分解一下就好了,应该是道模板题

然而我忘记还有质因数只有一个的情况,L不能等于N啊

QvQ拍了好久都没找到错在哪,后来随手输了个1024发现事情有蹊跷…

#include<iostream>#include<cstdio>#include<cstring>#include<cstdlib>#include<vector>#include<map>using namespace std;typedef long long LL;LL T,ans=0;vector<LL>v;map<LL,LL>num;LL gcd(LL a,LL b){    return b?gcd(b,a%b):a;}LL mul(LL a,LL b,LL p){    LL res=0;    while(b)    {        if(b&1)res=(res+a)%p;        a=(a+a)%p;b>>=1;    }    return res;}LL pow(LL a,LL n,LL p){    LL res=1;    while(n)    {        if(n&1)res=mul(res,a,p);        a=mul(a,a,p);n>>=1;    }    return res;}bool check(LL a,LL n,LL m,LL cnt){    LL x=pow(a,m,n),y=x;    for(int i=1;i<=cnt;i++)    {        x=mul(x,x,n);        if(x==1&&y!=1&&y!=x-1)return 1;        y=x;    }    return x!=1;}bool Miller_Rabin(LL n){    if(n==2)return 1;    if(n<=1||n&1==0)return 0;    LL m=n-1,cnt=0;    while(m&1==0)cnt++,m>>=1;    for(int i=1;i<=7;i++)    {        if(check(rand()%(n-1)+1,n,m,cnt))        return 0;    }    return 1;}LL rho(LL n,LL c){    LL i=1,k=2,x=rand()%(n-1)+1,y=x,d;    while(1)    {        x=(mul(x,x,n)+c)%n;        d=x>y?gcd(x-y,n):gcd(y-x,n);        if(d>1)return d;        if(y==x)return n;        if(i==k)y=x,k<<=1;        i++;    }}void solve(LL n){    if(n==1)return;    if(Miller_Rabin(n))    {        if(!num[n])        {v.push_back(n),ans++,num[n]=1;}        num[n]*=n;        return;    }    LL p=n;    while(p==n)p=rho(n,rand()%(n-1)+1);    solve(p);solve(n/p);}int main(){    scanf("%lld",&T);    while(T--)    {        LL n;        scanf("%lld",&n);        v.clear(),num.clear(),ans=0;        solve(n);        if(v[0]==n)ans--;        printf("%lld ",ans);        LL sum=0;        for(int i=0;i<ans;i++)        sum+=num[v[i]];        if(ans==1)sum/=v[0];        printf("%lld\n",sum);    }    return 0;}

 

[HDU 4344]Mark the Rope(Pollard_rho+Miller_Rabin)