結果
問題 |
No.3028 No.9999
|
ユーザー |
|
提出日時 | 2025-02-21 21:56:17 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 4,000 ms |
コード長 | 702 bytes |
コンパイル時間 | 2,511 ms |
コンパイル使用メモリ | 193,348 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2025-02-21 21:56:21 |
合計ジャッジ時間 | 3,664 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; ll phi(ll N) { ll ret = N; ll p = 2; while (p * p <= N) { if (N % p == 0) { ret /= p; ret *= (p - 1); while (N % p == 0) { N /= p; } } p ++; } if (N > 1) { ret /= N; ret *= (N-1); } return ret; } ll mpow(ll a, ll n, ll m) { ll ret = 1; while (n) { if (n & 1) { ret = (ret * a) % m; } n >>= 1; a = (a * a) % m; } return ret; } int main () { ll N; cin >> N; ll K = phi(N); ll ans = K; for (ll i = 1; i * i <= K; i ++) { if (K % i) continue; if (mpow(10, i, N) == 1) { ans = min(ans, i); } if (mpow(10, K/i, N) == 1) { ans = min(ans, K/i); } } cout << ans << endl; }