結果
問題 |
No.3028 No.9999
|
ユーザー |
![]() |
提出日時 | 2025-03-04 19:41:17 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 4,000 ms |
コード長 | 1,359 bytes |
コンパイル時間 | 2,635 ms |
コンパイル使用メモリ | 201,916 KB |
実行使用メモリ | 8,608 KB |
最終ジャッジ日時 | 2025-03-04 19:41:21 |
合計ジャッジ時間 | 3,976 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; ll modPow(ll b, ll e, ll m) { ll res = 1 % m; b %= m; while(e){ if(e & 1) res = (res * b) % m; b = (b * b) % m; e >>= 1; } return res; } vector<pair<int,int>> factorize(int n){ vector<pair<int,int>> f; for (int i=2; i*i <= n; i++){ if(n % i == 0){ int cnt = 0; while(n % i == 0){ cnt++; n /= i; } f.push_back({i, cnt}); } } if(n > 1) f.push_back({n, 1}); return f; } vector<int> divisors(int n) { vector<int> div; for (int i = 1; i*i <= n; i++){ if(n % i == 0){ div.push_back(i); if(i * i != n) div.push_back(n / i); } } sort(div.begin(), div.end()); return div; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; if(n == 1){ cout << 1 << endl; return 0; } // φ(n) を n の素因数分解から計算 int nn = n; auto f = factorize(nn); int phi = n; for(auto &p: f) phi = phi / p.first * (p.first - 1); auto divs = divisors(phi); for(auto d : divs){ if(modPow(10, d, n) == 1){ cout << d << endl; break; } } return 0; }