結果
問題 | No.1255 ハイレーツ・オブ・ボリビアン |
ユーザー |
![]() |
提出日時 | 2020-10-09 22:05:51 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 93 ms / 2,000 ms |
コード長 | 931 bytes |
コンパイル時間 | 686 ms |
コンパイル使用メモリ | 67,876 KB |
最終ジャッジ日時 | 2025-01-15 04:45:29 |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 15 |
ソースコード
#include <iostream> using namespace std; typedef long long ll; ll phi(ll x){ ll eu = x; for(ll i=2;i*i<=x;i++){ if(x%i==0) eu /= i,eu *= (i - 1); while(x%i==0) x /= i; } if(x!=1) eu /= x,eu *= (x - 1); return eu; } bool solve(ll a,ll x,ll mod){ ll ret = 1; while(x){ if(x&1) (ret *= a) %= mod; (a *= a) %= mod; x /= 2; } return ret==1; } int main(){ int t; cin >> t; while(t){ t--; ll i,n; cin >> n; n = 2*n - 1; ll m = phi(n); ll ans = m + 1; if(n==1){ cout << 1 << endl; }else{ for(i=1;i*i<=m;i++){ if(m%i==0){ if(solve(2,i,n)) ans = min(ans,i); if(solve(2,m/i,n)) ans = min(ans,m/i); } } if(ans>m) cout << -1 << endl; else cout << ans << endl; } } }