結果
問題 |
No.3115 One Power One Kill
|
ユーザー |
![]() |
提出日時 | 2025-08-26 03:19:25 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 65 ms / 2,000 ms |
コード長 | 1,512 bytes |
コンパイル時間 | 2,967 ms |
コンパイル使用メモリ | 277,616 KB |
実行使用メモリ | 26,252 KB |
平均クエリ数 | 2.00 |
最終ジャッジ日時 | 2025-08-26 03:19:31 |
合計ジャッジ時間 | 6,157 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 20 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/modint> using namespace std; using namespace atcoder; using ll = long long; using mint = modint1000000007; int main(){ cin.tie(nullptr); ios_base::sync_with_stdio(false); /* Bを素数とする。 また、AをB-1の倍数とすると、 XがBの倍数でないとき、フェルマーの小定理より、 X^A mod B = 0 KからXがBの倍数かどうか知るには? YがBの倍数であるならば、 K = gcd(X, Y)がBの倍数であるならば、XはBの倍数であることがわかり KがBの倍数でないならば、XはBの倍数でない。 よって、YがBの倍数であるような、A, Bのペアを見つければ良い。 */ /* int N=100000; vector<bool> prime(N+1, 1); for (int i=2; i<=N; i++){ if (prime[i]){ for (int j=i*2; j<=N; j+=i) prime[j] = 0; } } vector<int> v; for (int i=100; i<=N; i++) if (prime[i]) v.push_back(i); for (auto b : v){ for (int a=b-1; a<=N; a+=(b-1)){ ll Y = mint(a).pow(b).val(); if (Y % b == 0){ cout << a << " " << b << endl; return 0; } } } */ ll A=19000, B=101, Y=mint(A).pow(B).val(); cout << A << " " << B << endl; ll K; cin >> K; if (K % B == 0) cout << 0 << endl; else cout << 1 << endl; ll v; cin >> v; assert(v == 1); return 0; }