結果

問題 No.3028 No.9999
コンテスト
ユーザー makichan
提出日時 2025-02-21 21:36:18
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 4,000 ms
コード長 4,033 bytes
コンパイル時間 7,645 ms
コンパイル使用メモリ 333,444 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2025-02-21 21:36:29
合計ジャッジ時間 8,195 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using mint = atcoder::static_modint<998244353>;
// // using mint = atcoder::static_modint<1000000007>;
using ld = long double;
using ll = long long;
#define mp(a,b) make_pair(a,b)
#define rep(i,s,n) for(int i=s; i<(int)n; i++)
const vector<int> dx{1,0,-1,0},dy{0,1,0,-1};

bool is_prime(ll x){
    // miller rabin
    auto pow_mod=[&](__int128_t a,ll k,__int128_t mod){
        __int128_t output=1;
        a%=mod;
        while(k){
            if(k&1)output=(output*a)%mod;
            a=(a*a)%mod;
            k>>=1;
        }
        return output;
    };
    if(x<=1)return false;
    vector<ll> test;
    if(x<4759123141)test={2,7,61};
    else test={2,325,9375,28178,450775,9780504,1795265022};

    ll K=x-1;
    while(!(K&1))K>>=1;

    for(ll a:test){
        if(a>=x)return true;
        bool ok=false;
        ll k=K;
        __int128_t c=pow_mod(a,k,x);
        if(c==1)ok=true;
        else{
            while(k<=x-1){
                if(c==x-1){
                    ok=true;
                    break;
                }
                c=c*c%x;
                k<<=1;
            }
        }
        if(!ok)return false;
    }
    return true;
}

vector<pair<ll,int>> factorize(ll n){
    // Pollard's rho
    vector<pair<ll,int>> output;
    rep(i,2,100){
        while(n%i==0){
            output.push_back(mp(i,0));
            while(n%i==0)n/=i,output.back().second++;
        }
        if(n==1)return output;
    }
    
    stack<ll> calc;
    random_device rd;
    mt19937 engine(rd());
    vector<ll> P;
    calc.push(n);
    while(calc.size()){
        n=calc.top();calc.pop();
        while(!is_prime(n)){
            __int128_t x=engine()%n,y=x;
            ll plus=engine()%n+1;
            int i=1;
            while(true){
                x=(x*x+plus)%n;
                y=(y*y+plus)%n;
                y=(y*y+plus)%n;

                ll d=x-y;d=abs(d);
                ll g=gcd(d,n);
                if(g==1)i++;
                else if(g==n)break;
                else{
                    if(is_prime(g))P.push_back(g);
                    else calc.push(g);
                    n/=g;
                    break;
                }
            }
        }
        P.push_back(n);
    }
    sort(P.begin(),P.end());
    for(auto p:P){
        if(output.size()==0 || output.back().first!=p)output.push_back(mp(p,1));
        else output.back().second++;
    }
    return output;
}

vector<pair<ll,int>> multiplicative_group(ll p,int k){
    // mod p^kの乗法群を巡回群に分解
    vector<pair<ll,int>> output;
    if(p==2){
        if(k==2)output.push_back(mp(2,1));
        else if(k>=3){
            output.push_back(mp(2,1));
            output.push_back(mp(2,k-2));
        }
    }
    else{
        auto v=factorize(p-1);
        for(auto pk:v)output.push_back(pk);
        if(k>1)output.push_back(mp(p,k-1));
        sort(output.begin(),output.end());
    }
    return output;
}

vector<pair<ll,int>> multiplicative_group_decomposition(vector<pair<ll,int>> P){
    // (p,k)=p^kの素因数分解の形をvectorで渡すと乗法群を巡回群に分解、sortして返すmultiplicative_group_decomposition(factorize(n))で動く
    vector<pair<ll,int>> output;
    for(auto [p,k]:P){
        auto v=multiplicative_group(p,k);
        for(auto pk:v)output.push_back(pk);
    }
    sort(output.begin(),output.end());
    return output;
}

int main(){
    ll n;cin >> n;
    if(n==1){
        cout << 1 << "\n";
        return 0;
    }
    auto P=multiplicative_group_decomposition(factorize(n));
    ll order=1;
    reverse(P.begin(),P.end());
    ll last=-1;
    vector<ll> Q;
    for(auto [p,k]:P){
        // cout << p << " " << k << "\n";
        if(p!=last){
            Q.push_back(p);
            rep(i,0,k)order*=p;
            last=p;
        }
    }
    // cout << order;

    for(auto p:Q){
        while(order%p==0 && pow_mod(10,order/p,n)==1)order/=p;
    }
    cout << order << "\n";
}
0