結果

問題 No.1255 ハイレーツ・オブ・ボリビアン
コンテスト
ユーザー fastmath
提出日時 2020-10-09 23:10:04
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 99 ms / 2,000 ms
コード長 2,350 bytes
コンパイル時間 1,849 ms
コンパイル使用メモリ 203,672 KB
最終ジャッジ日時 2025-01-15 05:45:13
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 15
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘long long int fast_solve()’:
main.cpp:57:1: warning: no return statement in function returning non-void [-Wreturn-type]
   57 | }
      | ^

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcountll
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC
#define debug(x) std::cout << #x << ": " << x << '\n';

int solve(int n) {
    vector <int> a(2 * n);
    for (int i = 0; i < 2 * n; ++i)
        a[i] = i;

    auto was = a;

    auto f = [&] (vector <int> a) {
        vector <int> ans;
        for (int i = 0; i < n; ++i) {
            ans.app(a[i]);
            ans.app(a[i + n]);
        }   
        return ans;
    };  

    int ans = 0;
    while (1) {
        a = f(a);
        ans++;
        if (a == was) {
            return ans;
        }   
    }   
    assert(0);
}

int phi (int n) {
    int result = n;
    for (int i=2; i*i<=n; ++i)
        if (n % i == 0) {
            while (n % i == 0)
                n /= i;
            result -= result / i;
        }
    if (n > 1)
        result -= result / n;
    return result;
}

int fast_solve() {

}   

int fp(int a, int p, int mod) {
    int ans = 1, cur = a;
    for (int i = 0; (1ll << i) <= p; ++i) {
        if ((p >> i) & 1) {
            ans = (ans * cur) % mod;
        }   
        cur = (cur * cur) % mod;
    }   
    return ans;
}    

signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    #define endl '\n'
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cout.setf(ios::fixed); cout.precision(20); 
    #endif

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;

        if (n == 1) {
            cout << 1 << endl;
            continue;
        }   

        int mod = 2 * n - 1;
        int ph = phi(mod);
        vector <int> a;
        for (int d = 1; d * d <= ph; ++d) {
            if (ph % d == 0) {
                a.app(d);
                a.app(ph/d);
            }   
        }   
        sort(all(a));
        for (auto e : a) {
            if (fp(2, e, mod) == 1) {
                cout << e << endl;
                break;
            }   
        }   
    }

    exit(0);

    /*
    for (int n = 1; n <= 100; ++n) {
        //cout << n << ' ' << solve(n) << endl;
        cout << solve(n) << ' ';
    }   
    cout << endl;
    */


}
0