結果

問題 No.1255 ハイレーツ・オブ・ボリビアン
コンテスト
ユーザー 👑 Kazun
提出日時 2022-06-05 03:37:03
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,203 ms / 2,000 ms
コード長 4,623 bytes
コンパイル時間 2,084 ms
コンパイル使用メモリ 202,120 KB
最終ジャッジ日時 2025-01-29 18:21:48
ジャッジサーバーID
（参考情報） 		judge2 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>

using namespace std;
using ll=long long;

struct Modulo{
    int64_t a;  int n;

    public:
    // 初期化
    Modulo(): a(0), n(1){}
    Modulo(int64_t a_, int n_){
        if (n_>0) a=(a_%n_+n_)%n_, n=n_;
        else a=0LL, n=0;
    }

    // マイナス元
    Modulo operator-() const {return Modulo(-a,n);}

    // 加法
    Modulo& operator+=(const Modulo &y){
        assert (n==y.n);
        if ((a+=y.a)>=n) a-=n;
        return *this;
    }

    Modulo& operator+=(const int64_t &y){return (*this)+=Modulo(y,n);}

    friend Modulo operator+(const Modulo &x, const Modulo &y) {return Modulo(x)+=y;}
    friend Modulo operator+(const Modulo &x, const int64_t &a) {return x+Modulo(a,x.n);}
    friend Modulo operator+(const int64_t &a, const Modulo &x) {return Modulo(a,x.n)+x;}

    // 減法
    Modulo& operator-=(const Modulo &y){
        assert (n==y.n);
        if ((a+=(n-y.a))>=n) a-=n;
        return *this;
    }

    Modulo& operator-=(const int64_t &y){return (*this)-=Modulo(y,n);}

    friend Modulo operator-(const Modulo &x, const Modulo &y) {return Modulo(x)-=y;}
    friend Modulo operator-(const Modulo &x, const int64_t &a) {return x-Modulo(a,x.n);}
    friend Modulo operator-(const int64_t &a, const Modulo &x) {return Modulo(a,x.n)-x;}

    // 乗法
    Modulo& operator*=(const Modulo &y){
        assert (n==y.n);
        (a*=y.a)%=n;
        return *this;
    }

    Modulo& operator*=(const int64_t &y){return (*this)*=Modulo(y,n);}

    friend Modulo operator*(const Modulo &x, const Modulo &y) {return Modulo(x)*=y;}
    friend Modulo operator*(const Modulo &x, const int64_t &a) {return x*Modulo(a,x.n);}
    friend Modulo operator*(const int64_t &a, const Modulo &x) {return Modulo(a,x.n)*x;}

    // 除法
    Modulo& operator/=(const Modulo &y){
        assert (n==y.n);
        return (*this)*=y.inverse();
    }

    Modulo& operator/=(const int64_t &y){return (*this)/=Modulo(y,n);}

    friend Modulo operator/(const Modulo &x, const Modulo &y) {return Modulo(x)/=y;}
    friend Modulo operator/(const Modulo &x, const int64_t &a) {return x/Modulo(a,x.n);}
    friend Modulo operator/(const int64_t &a, const Modulo &x) {return Modulo(a,x.n)/x;}

    // 退化
    Modulo& degenerate(const int m){
        assert (n%m==0);
        a%=m; n=m;
        return *this;
    }

    // モジュラー逆元
    bool invertible() const {
        int64_t x=a, y=n;
        while (y) swap(x=x%y,y);
        return x==1;
    }

    Modulo inverse() const{
        int64_t s=1, t=0;
        int64_t x=a, y=n;
        while (y){
            auto q=x/y;
            swap(x-=q*y,y);
            swap(s-=q*t,t);
        }
        assert(x==1);

        return Modulo(s,n);
    }

    // 比較
    friend bool operator==(const Modulo &x, const Modulo &y) {return x.a==y.a;}
    friend bool operator==(const Modulo &x, const int64_t &a) {return (x.a-a)%x.n==0;}
    friend bool operator==(const int64_t &a, const Modulo &x) {return (a-x.a)%x.n==0;}

    friend bool operator!=(const Modulo &x, const Modulo &y) {return x.a!=y.a;}
    friend bool operator!=(const Modulo &x, const int64_t &a) {return (x.a-a)%x.n!=0;}
    friend bool operator!=(const int64_t &a, const Modulo &x) {return (a-x.a)%x.n!=0;}

    // 入力
    friend istream &operator>>(istream &is, Modulo &x) {
        int64_t b; int m;
        is >> b >> m;
        x=Modulo(b,m);
        return (is);
    }

    // 出力
    friend ostream &operator<<(ostream &os, const Modulo &x) { return os << x.a << " (mod " << x.n << ")";}
};

//離散対数
int64_t Discrete_Logarithm(Modulo X, Modulo Y){
    assert(X.n==Y.n);

    int64_t f,g,m;
    Modulo R(1,X.n);

    // Step 1: 可逆元の累乗に持ち込む

    for (f=0; (g=gcd(X.a,X.n))>1; f++){
        if (Y.a%g) return (R==Y) ? f: -1;

        m=X.n/g;

        R*=X.a/g; R.degenerate(m);
        X.degenerate(m);
        Y.a/=g; Y.degenerate(m);
    }

    if (X.n==1) return f;

    Y/=R;

    // Step 2-a: Baby-Step
    int64_t t=0;
    Modulo H(1,X.n);
    unordered_map<int64_t, int64_t> B;

    for (; t*t<X.n; t++){
        if (B.find(H.a)==B.end()) B[H.a]=t;
        H*=X;
    }

    // Step 2-b: Giant-Step
    Modulo H_inv=H.inverse();
    for (int64_t j=0; j<t; j++){
        if (B.find(Y.a)!=B.end()) return f+j*t+B[Y.a];
        Y*=H_inv;
    }

    return -1;
}

// 位数
int64_t Order(const Modulo &X){
    return (X.invertible()) ? Discrete_Logarithm(X, X.inverse())+1: -1;
}

int main(){
    int T; cin >> T;
    for (int t=0; t<T; t++){
        int N; cin >> N;
        cout << Order(Modulo(2,2*N-1)) << "\n";
    }
}
0