結果
問題 | No.1255 ハイレーツ・オブ・ボリビアン |
ユーザー | kotatsugame |
提出日時 | 2020-10-09 22:05:38 |
言語 | C++14 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 64 ms / 2,000 ms |
コード長 | 1,072 bytes |
コンパイル時間 | 522 ms |
コンパイル使用メモリ | 66,692 KB |
実行使用メモリ | 4,380 KB |
最終ジャッジ日時 | 2023-09-30 14:41:37 |
合計ジャッジ時間 | 1,489 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge12 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,376 KB |
testcase_01 | AC | 2 ms
4,376 KB |
testcase_02 | AC | 1 ms
4,380 KB |
testcase_03 | AC | 2 ms
4,376 KB |
testcase_04 | AC | 2 ms
4,380 KB |
testcase_05 | AC | 3 ms
4,376 KB |
testcase_06 | AC | 2 ms
4,376 KB |
testcase_07 | AC | 2 ms
4,376 KB |
testcase_08 | AC | 14 ms
4,380 KB |
testcase_09 | AC | 16 ms
4,376 KB |
testcase_10 | AC | 15 ms
4,380 KB |
testcase_11 | AC | 15 ms
4,376 KB |
testcase_12 | AC | 15 ms
4,376 KB |
testcase_13 | AC | 3 ms
4,376 KB |
testcase_14 | AC | 64 ms
4,376 KB |
testcase_15 | AC | 13 ms
4,376 KB |
コンパイルメッセージ
main.cpp:41:1: 警告: ISO C++ では型の無い ‘main’ の宣言を禁止しています [-Wreturn-type] 41 | main() | ^~~~
ソースコード
#include<iostream> using namespace std; int T,N; long gcd(long a,long b){return b?gcd(b,a%b):a;} long L(long N) { if(!(N&N-1)) { if(N==1)return 1; else if(N==2)return 1; else if(N==4)return 2; else return N>>2; } long T=1; for(long i=2;i*i<=N;i++) { if(N%i==0) { long x=1; while(N%i==0) { N/=i; x*=i; } if(N>1)x=L(x); else { x=x/i*(i-1); } T=T/gcd(T,x)*x; } } if(N>1) { long x=N-1; T=T/gcd(T,x)*x; } return T; } long modpow(long a,long b,long M){return b?modpow(a*a%M,b/2,M)*(b%2?a:1)%M:1;} main() { cin>>T; for(int i=1;i<=T;i++) { cin>>N; if(N==1) { cout<<1<<endl; continue; } int ans; /*N=2*N-1; ans=N-1; for(int i=1;i*i<=N-1;i++) { if((N-1)%i==0) { if(ans>i&&modpow(2,i,N)==1)ans=i; if(i!=(N-1)/i&&ans>(N-1)/i&&modpow(2,(N-1)/i,N)==1)ans=(N-1)/i; } }*/ int X=ans=L(2*N-1); for(int i=1;i*i<=X;i++) { if(X%i==0) { if(ans>i&&modpow(2,i,2*N-1)==1)ans=i; if(i!=X/i&&ans>X/i&&modpow(2,X/i,2*N-1)==1)ans=X/i; } } cout<<ans<<endl; } }