結果
問題 | No.1339 循環小数 |
ユーザー | snrnsidy |
提出日時 | 2021-08-07 16:52:49 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 42 ms / 2,000 ms |
コード長 | 2,702 bytes |
コンパイル時間 | 2,653 ms |
コンパイル使用メモリ | 219,364 KB |
実行使用メモリ | 4,348 KB |
最終ジャッジ日時 | 2023-10-18 23:35:52 |
合計ジャッジ時間 | 4,358 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,348 KB |
testcase_01 | AC | 2 ms
4,348 KB |
testcase_02 | AC | 2 ms
4,348 KB |
testcase_03 | AC | 2 ms
4,348 KB |
testcase_04 | AC | 2 ms
4,348 KB |
testcase_05 | AC | 3 ms
4,348 KB |
testcase_06 | AC | 2 ms
4,348 KB |
testcase_07 | AC | 3 ms
4,348 KB |
testcase_08 | AC | 3 ms
4,348 KB |
testcase_09 | AC | 3 ms
4,348 KB |
testcase_10 | AC | 3 ms
4,348 KB |
testcase_11 | AC | 4 ms
4,348 KB |
testcase_12 | AC | 3 ms
4,348 KB |
testcase_13 | AC | 4 ms
4,348 KB |
testcase_14 | AC | 4 ms
4,348 KB |
testcase_15 | AC | 3 ms
4,348 KB |
testcase_16 | AC | 4 ms
4,348 KB |
testcase_17 | AC | 3 ms
4,348 KB |
testcase_18 | AC | 3 ms
4,348 KB |
testcase_19 | AC | 3 ms
4,348 KB |
testcase_20 | AC | 4 ms
4,348 KB |
testcase_21 | AC | 23 ms
4,348 KB |
testcase_22 | AC | 24 ms
4,348 KB |
testcase_23 | AC | 24 ms
4,348 KB |
testcase_24 | AC | 23 ms
4,348 KB |
testcase_25 | AC | 25 ms
4,348 KB |
testcase_26 | AC | 24 ms
4,348 KB |
testcase_27 | AC | 25 ms
4,348 KB |
testcase_28 | AC | 24 ms
4,348 KB |
testcase_29 | AC | 22 ms
4,348 KB |
testcase_30 | AC | 22 ms
4,348 KB |
testcase_31 | AC | 41 ms
4,348 KB |
testcase_32 | AC | 42 ms
4,348 KB |
testcase_33 | AC | 27 ms
4,348 KB |
testcase_34 | AC | 9 ms
4,348 KB |
testcase_35 | AC | 32 ms
4,348 KB |
testcase_36 | AC | 25 ms
4,348 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; map <long long int, long long int> phi; vector <long long int> prime; long long int mypow(long long int x, long long int n) { long long int res = 1; while (n > 0) { if (n % 2 == 1) { res = ((res) * (x)); } x = (x * x); n /= 2; } return res; } void eratos(void) { bool isprime[32001]; memset(isprime, true, sizeof(isprime)); for (int i = 2; i <= 32000; i++) { if (isprime[i]) { prime.push_back(i); for (int j = 2 * i; j <= 32000; j += i) { isprime[j] = false; } } } } long long int mypow(long long int x, long long int n, long long int m) { long long int res = 1; while (n > 0) { if (n % 2 == 1) { res = ((res % m) * (x % m) % m); res %= m; } x = ((x % m) * (x % m) % m); x %= m; n /= 2; } return res; } int main(void) { cin.tie(0); ios::sync_with_stdio(false); int N, t; vector <int> v; cin >> N; for (int i = 0; i < N; i++) { cin >> t; while (t % 2 == 0) { t /= 2; } while (t % 5 == 0) { t /= 5; } v.push_back(t); } eratos(); for(int i=0;i<N;i++) { map <int, int> m; int n; long long int res = 1; n = v[i]; while (1) { bool ok = false; for (int i = 2; i <= sqrt(n); i++) { if (n % i == 0) { ok = true; m[i]++; n /= i; break; } } if (ok == false) { m[n]++; break; } } for (auto x : m) { res *= (pow(x.first, x.second) - pow(x.first, x.second - 1)); } phi[v[i]] = res; } for (int i = 0; i < N; i++) { if (v[i] == 1) { cout << 1 << '\n'; continue; } int temp = phi[v[i]]; int res = 1e9; for (int j = 1; j <= sqrt(temp); j++) { if (temp % j == 0) { if (mypow(10, j, v[i]) == 1) { res = min(res, j); } if (mypow(10, temp / j, v[i]) == 1) { res = min(res, temp / j); } } } cout << res << '\n'; } return 0; }