結果

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

ソースコード

diff # 

#include<bits/stdc++.h>

using namespace std;
using ll=long long;

// 素因数分解 O(sqrt(N))
vector<pair<long long,long long>> Prime_Factorization(long long N){
	vector<pair<long long,long long>> T;

	if (N%2==0){
		int k=0;
		while (N%2==0){k++; N/=2;}
		T.emplace_back(make_pair(2,k));
	}

	if (N%3==0){
		int k=0;
		while (N%3==0){k++; N/=3;}
		T.emplace_back(make_pair(3,k));
	}

	int flag=0;
	for (long long p=5; p*p<=N; p+=2+2*flag, flag^=1){
		if (N%p==0){
			int k=0;
			while (N%p==0){k++; N/=p;}
			T.emplace_back(make_pair(p,k));
		}
	}

	if (N!=1) T.emplace_back(make_pair(N,1));

	return T;
}

// 約数列挙
vector<long long> Divisors(long long N){
	vector<long long> D;
	for (long long i=1; i*i<=N; i++){
		if (N%i==0){
			D.push_back(i);
			if (i*i!=N){D.push_back(N/i);}
		}
	}

	sort(D.begin(), D.end());
	return D;
}

long long Euler_Totient(long long N){
    /*1 以上 N 以下の整数のうち, N と互いに素な整数の個数 φ(N) を求める.*/

    assert  (N>=0);
    long long p,phi=N;
    for (auto x: Prime_Factorization(N)) p=x.first, (phi/=p)*=p-1;
    return phi;
}

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 << ")";}
};

Modulo pow(Modulo x, int64_t n){
    if (n<0) return pow(x,-n).inverse();

    Modulo y(1, x.n);
    while (n){
        if (n&1) y*=x;
        x*=x; n>>=1;
    }

    return y;
}

// 位数
int64_t Order(const Modulo &X){
    if (X.invertible()){
        for (auto k: Divisors(Euler_Totient(X.n))){
            if (pow(X,k)==1) return k;
        }
        return -1;
    }
    else return -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