結果
問題 | No.1255 ハイレーツ・オブ・ボリビアン |
ユーザー | beet |
提出日時 | 2020-10-09 22:10:53 |
言語 | C++17 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 99 ms / 2,000 ms |
コード長 | 2,197 bytes |
コンパイル時間 | 2,225 ms |
コンパイル使用メモリ | 206,484 KB |
実行使用メモリ | 4,380 KB |
最終ジャッジ日時 | 2023-09-30 14:41:53 |
合計ジャッジ時間 | 3,189 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,376 KB |
testcase_01 | AC | 2 ms
4,380 KB |
testcase_02 | AC | 1 ms
4,376 KB |
testcase_03 | AC | 1 ms
4,380 KB |
testcase_04 | AC | 2 ms
4,376 KB |
testcase_05 | AC | 2 ms
4,376 KB |
testcase_06 | AC | 3 ms
4,380 KB |
testcase_07 | AC | 2 ms
4,380 KB |
testcase_08 | AC | 22 ms
4,376 KB |
testcase_09 | AC | 24 ms
4,380 KB |
testcase_10 | AC | 21 ms
4,376 KB |
testcase_11 | AC | 22 ms
4,380 KB |
testcase_12 | AC | 21 ms
4,376 KB |
testcase_13 | AC | 4 ms
4,380 KB |
testcase_14 | AC | 99 ms
4,380 KB |
testcase_15 | AC | 18 ms
4,380 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; using Int = long long; const char newl = '\n'; template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;} template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;} template<typename T> void drop(const T &x){cout<<x<<endl;exit(0);} template<typename T=Int> vector<T> read(size_t n){ vector<T> ts(n); for(size_t i=0;i<n;i++) cin>>ts[i]; return ts; } vector<Int> identity(Int n){ vector<Int> ord(n); iota(ord.begin(),ord.end(),0); return ord; } template<typename T> T mod_pow(T a,long long n,T mod){ using ll = long long; T res(1); while(n){ if(n&1) res=(ll)res*a%mod; a=(ll)a*a%mod; n>>=1; } return res; } // min m s.t. a^m = 1 mod n (a, n are coprime) template<typename T> T carmichael_lambda(T n){ auto lcm=[](auto a,auto b){return a/__gcd(a,b)*b;}; T res=1; if(n%8==0) n/=2; for(int i=2;i*i<=n;i++){ if(n%i==0){ T tmp=i-1; for(n/=i;n%i==0;n/=i) tmp*=i; res=lcm(res,tmp); } } if(n!=1) res=lcm(res,n-1); return res; } template<typename T> T order(T x,T MOD){ T res=carmichael_lambda(MOD); vector<T> cand; for(T i=1;i*i<=res;i++){ if(res%i) continue; cand.emplace_back(i); cand.emplace_back(res/i); } sort(cand.begin(),cand.end()); for(T c:cand) if(mod_pow(x,c,MOD)==1) return c; return res; } //INSERT ABOVE HERE signed main(){ cin.tie(0); ios::sync_with_stdio(0); auto solve=[](Int n){ return order<Int>(2,2*n-1); /* Int res=0,tmp=1; do{ tmp+=2*n-1; while(tmp%2==0) tmp/=2,res++; }while(tmp!=1); return res; */ }; auto naive=[&](Int n){ vector<Int> as=identity(2*n); Int cnt=0; do{ cnt++; vector<Int> bs(as); for(Int i=0;i<n;i++){ as[i*2+0]=bs[0+i]; as[i*2+1]=bs[n+i]; } }while(as!=identity(2*n)); return cnt; }; const Int EXPERIMENT = 0; if(EXPERIMENT){ for(Int n=1;n<=30;n++){ cout<<n<<':'<<naive(n)<<':'<<solve(n)<<newl; assert(naive(n)==solve(n)); } } Int T; cin>>T; while(T--){ Int n; cin>>n; cout<<solve(n)<<newl; } return 0; }