SP4948题解

· · 题解

题目传送门。

本题主要考查 Pollard-Rho 算法。

思路

题目意思就是叫你分解质因数，没有别的东西了。

对于每一个质因子，暴力算出它的指数，注意这里是顺序输出质因子，我们只用浅浅排序一下即可。

对于 Pollard-Rho 算法，这里浅谈一下，本质上是随机化，利用生日悖论来提高算法的正确率。随机选出两个数 x,y，两个数的差的绝对值有很大可能为 N 的因子，即 \gcd(\left|x-y\right|,N)>1，可以利用 Floyd 判圈法提升速度，期望时间复杂度为 O(n^{\frac{1}{4}})。

普通判断质数太慢了，因此我们需要一个更为高效的算法 Miller_Rabin，详细可以看这篇文章 this。

有以下图：

这也就说明为什么算法名有一个 \rho 了。

注意事项

  1. 本题数据需要开到 10^{29}，需要用 __int128 储存。

  2. 不建议使用快速乘，可以使用 ll mul(ll a,ll b,ll p){return (a*b-(ll)((__float128)a/p*b)*p+p)%p;}

接下来就是简简单单的卡常操作。

贴贴代码

#include <bits/stdc++.h>
#define ll __int128
#define Auto vector<ll>::iterator
using namespace std;
const ll Maxn=610,inf=0x3f3f3f3f;
vector<ll>S;
inline ll qread(){
    ll x=0;int f=1;char ch;
    while((ch=getchar())<'0'||ch>'9') if(ch=='-') f=0;x=(ch^48);
    while((ch=getchar())>='0'&&ch<='9') x=x*10+(ch^48);
    return f?x:-x;
}
inline void print(ll x){
    if(x>9) print(x/10);
    putchar('0'+(x%10));
}
namespace Math{
    ll mul(ll a,ll b,ll p){return (a*b-(ll)((__float128)a/p*b)*p+p)%p;}
    ll Abs(ll x){return x>0?x:-x;}
    inline ll ksm(ll a,ll b,ll p){
        a%=p;
        ll res=1;
        for(;b;b>>=1,a=mul(a,a,p))if(b&1)res=mul(res,a,p);
        return res;
    }
    inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
}
using namespace Math;
namespace Miller_Rabin{
    inline bool mr(ll x,ll b){
    ll k=x-1;
    while(k){
        ll cur=ksm(b,k,x);
        if(cur!=1&&cur!=x-1)return false;
        if((k&1)||cur==x-1)return true;
        k>>=1;
    }
    return true;
    }
    inline bool Prime(ll x){
        if(x<=1)return false;
        if(x==2||x==61)return true;
        return mr(x,2)&&mr(x,61);
    }
}
using namespace Miller_Rabin;
namespace Pollard_Rho{
    #define rnd() rand()
    inline ll f(ll x,ll c,ll n){
        return (mul(x,x,n)+c)%n;
    }
    inline ll PR(ll x){
        ll s=0,t=0,c=rnd()%(x-1)+1,val=1;
        for(int goal=1;;goal<<=1,s=t,val=1){
            for(int stp=1;stp<=goal;stp++){
                t=f(t,c,x);
                val=mul(val,Abs(t-s),x);
                if(stp%127==0){
                    ll d=__gcd(val,x);
                    if(d>1)return d;
                }
            }
            ll d=__gcd(val,x);
            if(d>1)return d;
        }
    }
    inline void solve(ll X){
        if(!(1^X)) return ;
        if(Prime(X)){S.push_back(X);return ;}
        ll Y=X;while(Y==X)Y=PR(X);while(!(X%Y)) X/=Y;
        solve(X);solve(Y);
    }
}
ll m,a,ans1=-inf,cnt;
int main(){
    srand(time(0));
    while(m=qread()){
        S.clear();Pollard_Rho::solve(m);
        sort(S.begin(),S.end());
        S.resize(unique(S.begin(),S.end())-S.begin());
        for(Auto it=S.begin();it!=S.end();it++){
            ll t=*it;
            print(t),printf("^");
            int k=0;while(m%t==0) m/=t,++k;
            printf("%d ",k);
        }   
        puts(" ");
    }
    return 0;
}