結果

問題 No.3028 No.9999
ユーザー makichan
提出日時 2025-02-22 00:09:41
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 5,524 bytes
コンパイル時間 8,029 ms
コンパイル使用メモリ 333,904 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2025-02-22 00:09:50
合計ジャッジ時間 8,290 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 3
other WA * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}

ll discrete_log(ll x,ll y,ll mod){
    // x^k=y(mod)を満たす最小のk,無いなら-1を返す
    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;
    };

    x%=mod,y%=mod;
    if(mod<=2){
        ll xpow=1%mod;
        rep(i,0,5){
            if(xpow==y)return i;
            xpow=xpow*x%mod;
        }
    }
    if(x==0){
        if(y==0)return 1;
        else if(y==1)return 0;
        else return -1;
    }
    if(gcd(x,mod)!=1){
        ll xpow=1;
        rep(i,0,64){
            if(xpow==y)return i;
            xpow=xpow*x%mod;
        }

        ll maxg=1;
        while(true){
            ll g=gcd(x,mod);
            if(g==1)break;
            maxg*=g;
            mod/=g;
        }
        if(y%maxg)return -1;
    }
    // xがmodの可逆元
    if(gcd(y,mod)!=1)return -1;

    //yも可逆元
    auto P=multiplicative_group_decomposition(factorize(mod));
    ll order=1;
    reverse(P.begin(),P.end());
    ll last=-1;
    for(auto[p,k]:P)if(last!=p){
        rep(i,0,k)order*=p;
        last=p;
    }
    // order=元の位数の最大

    // baby-giant
    ll sq=sqrt(order)+5;
    vector<pair<ll,ll>> list;
    rep(i,0,sq){
        ll c=pow_mod(x,sq*i,mod);
        list.push_back(mp(c,sq*i));
    }
    sort(list.begin(),list.end());
    list.push_back(mp(mod+1,0));//防人

    ll xinv=pow_mod(x,order-1,mod);
    ll Xinvpow=1;

    const ll inf=1e18;
    ll output=inf;
    rep(i,0,sq){
        ll target=y*Xinvpow%mod;
        int id=lower_bound(list.begin(),list.end(),mp(target,0LL))-list.begin();
        if(list[id].first==target){
            ll ans=i+list[id].second;
            output=min(output,ans);
        }
        Xinvpow=Xinvpow*xinv%mod;
    }
    if(output==inf)output=-1;
    return output;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;cin >> n;
    cout << discrete_log(10,1,n);
}
0