結果
問題 | No.1339 循環小数 |
ユーザー |
![]() |
提出日時 | 2021-01-15 23:03:29 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 63 ms / 2,000 ms |
コード長 | 1,635 bytes |
コンパイル時間 | 864 ms |
コンパイル使用メモリ | 78,148 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-26 17:10:06 |
合計ジャッジ時間 | 2,183 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 36 |
ソースコード
//諦めてググった: http://math.sakura.ne.jp/?action=common_download_main&upload_id=1377#include <iostream>#include <vector>#include <algorithm>#define int long longusing namespace std;int powmod(int a, int n, int mod) {if (n == 0) return 1;if (n % 2 == 1) return a * powmod(a, n - 1, mod) % mod;return powmod((a * a) % mod, n / 2, mod);}int f(int p) {vector<int> yaku;for (int i = 1; i * i <= p - 1; i++) {if ((p - 1) % i == 0) {yaku.push_back(i);if (i * i != p - 1) yaku.push_back((p - 1) / i);}}sort(yaku.begin(), yaku.end());int C = 1000;int m1 = powmod(10, C, p);for (int i = 0; i < yaku.size(); i++) {if (powmod(10, C + yaku[i], p) == m1) {return yaku[i];}}return -1;}int gcd(int a, int b) {if (b == 0) return a;return gcd(b, a % b);}int lcm(int a, int b) {return a / gcd(a, b) * b;}signed main() {int T;cin >> T;while (T--) {int n;cin >> n;vector<int> ps;vector<int> e;for (int i = 2; i * i <= n; i++) {if (n % i == 0) {ps.push_back(i);int cnt = 0;while (n % i == 0) {cnt++;n /= i;}e.push_back(cnt);}}if (n > 1) { ps.push_back(n); e.push_back(1); }int l = 1;for (int i = 0; i < ps.size(); i++) {int res;if (ps[i] == 2 || ps[i] == 5) continue;if (e[i] == 1) {res = f(ps[i]);}else if (ps[i] == 3 || ps[i] == 487) {res = f(ps[i]);for (int j = 0; j < e[i] - 2; j++) res *= ps[i];}else {res = f(ps[i]);for (int j = 0; j < e[i] - 1; j++) res *= ps[i];}l = lcm(l, res);}cout << l << endl;}return 0;}