アルゴ式（beta版）: C++による「整数論的アルゴリズム (beta)」番外編：高等アルゴリズムの解答例

アルゴ式（beta版）の「整数論的アルゴリズム (beta)」番外編：高等アルゴリズムからの出典です。
algo-method.com
アルゴ式とは...
>・プログラミングや情報科学をコツコツ学べる「教科書」
>・学んだ内容をゲーム感覚で大量に実践できる「練習問題」
>の２つで構成される、Web上で完結した学習コンテンツです。

C++による「整数論的アルゴリズム (beta)」番外編：高等アルゴリズムの解答例

僕が作成、提出したコードは、以下のとおりです。

ミラー-ラビン素数判定法

algo-method.com

/*
C++による「整数論的アルゴリズム (beta)」番外編：高等アルゴリズムの解答例
ミラー-ラビン素数判定法
https://algo-method.com/tasks/513
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
ll mm(ll a,ll b,ll mod){
    ll r=0;
    if(a<b){
        swap(a,b);
    }
    while(b>0){
        if(b&1){
            r=(r+a)%mod;
        }
        a=(2*a)%mod;
        b/=2;
    }
    return r;
}
ll pm(ll l,ll p,ll mod){
    ll r=1;
    while(p>0){
        if(p&1){
            r=mm(r,l,mod);
        }
        l=mm(l,l,mod);
        p/=2;
    }
    return r;
}
bool MR(ll n){ //MR <- Miller Rabin
    ll d=n-1;
    while((d&1)==0){
        d/=2;
    }
    for(ll i : {2,3,5,7,9,11,13,17,19,23}){
        ll j=d;
        ll k=pm(i,j,n);
        while(j!=n-1 && k!=0 && k!=1 && k!=n-1){
            k=mm(k,k,n);
            j<<=1;
        }
        if(k!=n-1 && (j&1)==0){
            return false;
        }
    }
    return true;
}
int main(void){
    ll n;
    cin>>n;
    vector<ll> a(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
        if(a[i]==2){
            cout<<"Yes"<<endl;
        }else if(a[i]%2==0 || a[i]==1){
            cout<<"No"<<endl;
        }else{
            cout<<((MR(a[i])) ? "Yes" : "No")<<endl;
        }
    }
    return 0;
}

・ポラードのロー素因数分解法

algo-method.com

/*
C++による「整数論的アルゴリズム (beta)」番外編：高等アルゴリズムの解答例
ポラードのロー素因数分解法
https://algo-method.com/tasks/553
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
ll mm(ll a,ll b,ll mod){
    ll r=0;
    if(a<b){
        swap(a,b);
    }
    while(b>0){
        if(b&1){
            r=(r+a)%mod;
        }
        a=(2*a)%mod;
        b/=2;
    }
    return r;
}
ll pm(ll l,ll p,ll mod){
    ll r=1;
    while(p>0){
        if(p&1){
            r=mm(r,l,mod);
        }
        l=mm(l,l,mod);
        p/=2;
    }
    return r;
}
bool MR_IP(ll n){ //MR_IP <- Miller Rabin-Is Prime
    ll d=n-1;
    while((d&1)==0){
        d/=2;
    }
    for(ll i : {2,3,5,7,9,11,13,17,19,23}){
        ll j=d;
        ll k=pm(i,j,n);
        while(j!=n-1 && k!=0 && k!=1 && k!=n-1){
            k=mm(k,k,n);
            j<<=1;
        }
        if(k!=n-1 && (j&1)==0){
            return false;
        }
    }
    return true;
}
ll basic(ll n){
    if(n%2==0){
        return 2;
    }
    if(MR_IP(n)){
        return n;
    }
    auto func=[&](ll l) -> ll{
        return (__int128_t(l)*l+1)%n;
    };
    ll cnt=0;
    while(1){
        cnt++;
        ll x=cnt;
        ll y=func(x);
        while(1){
            ll z=gcd(y-x+n,n);
            if(z==0 || z==n){
                break;
            }
            if(z!=1){
                return z;
            }
            x=func(x);
            y=func(func(y));
        }
    }
}
vector<ll> PR_PF(ll n){ //PR_PF <- Pollard's Rho_Prime Factorize
    if(n==1){
        return {};
    }
    ll l=basic(n);
    if(l==n){
        return {l};
    }
    vector<ll> left=PR_PF(l);
    vector<ll> right=PR_PF(n/l);
    left.insert(left.end(),right.begin(),right.end());
    sort(left.begin(),left.end());
    return left;
}
int main(void){
    ll n;
    cin>>n;
    vector<ll> a(n);
    for(ll i=0;i<n;i++){
        cin>>a[i];
    }
    for(auto i : a){
        const auto& j=PR_PF(i);
        for(auto k : j){
            cout<<k<<" ";
        }
        cout<<endl;
    }
    return 0;
}

設問の出典は、情報科学をコツコツ積み立てて学習できるサービス「アルゴ式（beta版）」です。
algo-method.com