結果
問題 | No.1339 循環小数 |
ユーザー |
|
提出日時 | 2021-03-14 01:27:26 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 47 ms / 2,000 ms |
コード長 | 1,038 bytes |
コンパイル時間 | 1,830 ms |
コンパイル使用メモリ | 192,528 KB |
最終ジャッジ日時 | 2025-01-19 16:14:46 |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 36 |
ソースコード
#include <bits/stdc++.h>using namespace std;long long totient(long long n) {long long ret = n;for (long long i = 2; i * i <= n; i++) {if (n % i == 0) {ret = ret / i * (i - 1);while (n % i == 0)n /= i;}}if (n != 1)ret = ret / n * (n - 1);return ret;}long long modpow(long long x, long long p, long long mod) {long long ret = 1;while (p) {if (p & 1)ret = ret * x % mod;x = x * x % mod;p >>= 1;}return ret;}int solve(int n) {while (n % 2 == 0) n /= 2;while (n % 5 == 0) n /= 5;if (n == 1)return 1;int t = totient(n);int ret = t;for (int x = 1; x * x <= t; x++) {if (t % x == 0) {if (modpow(10, x, n) == 1) ret = min(ret, x);if (modpow(10, t/x, n) == 1) ret = min(ret, t/x);}}return ret;}int main() {ios_base::sync_with_stdio(0);cin.tie(0);int T;cin >> T;while (T--) {int n;cin >> n;cout << solve(n) << endl;}return 0;}