結果
問題 | No.1339 循環小数 |
ユーザー | KY2001 |
提出日時 | 2021-01-15 22:02:56 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 4,216 bytes |
コンパイル時間 | 2,253 ms |
コンパイル使用メモリ | 208,416 KB |
実行使用メモリ | 12,476 KB |
最終ジャッジ日時 | 2024-05-04 23:50:55 |
合計ジャッジ時間 | 5,913 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
10,624 KB |
testcase_01 | AC | 5 ms
5,376 KB |
testcase_02 | AC | 4 ms
5,376 KB |
testcase_03 | AC | 4 ms
5,376 KB |
testcase_04 | AC | 4 ms
5,376 KB |
testcase_05 | AC | 5 ms
5,376 KB |
testcase_06 | AC | 6 ms
5,376 KB |
testcase_07 | AC | 4 ms
5,376 KB |
testcase_08 | AC | 5 ms
5,376 KB |
testcase_09 | AC | 6 ms
5,376 KB |
testcase_10 | AC | 4 ms
5,376 KB |
testcase_11 | TLE | - |
testcase_12 | -- | - |
testcase_13 | -- | - |
testcase_14 | -- | - |
testcase_15 | -- | - |
testcase_16 | -- | - |
testcase_17 | -- | - |
testcase_18 | -- | - |
testcase_19 | -- | - |
testcase_20 | -- | - |
testcase_21 | -- | - |
testcase_22 | -- | - |
testcase_23 | -- | - |
testcase_24 | -- | - |
testcase_25 | -- | - |
testcase_26 | -- | - |
testcase_27 | -- | - |
testcase_28 | -- | - |
testcase_29 | -- | - |
testcase_30 | -- | - |
testcase_31 | -- | - |
testcase_32 | -- | - |
testcase_33 | -- | - |
testcase_34 | -- | - |
testcase_35 | -- | - |
testcase_36 | -- | - |
ソースコード
/** * code generated by JHelper * More info: https://github.com/AlexeyDmitriev/JHelper * @author Kein Yukiyoshi */ // clang-format off #include <bits/stdc++.h> //#pragma GCC optimize("Ofast") //#pragma GCC target("avx") #define int long long using namespace std; #define stoi stoll #define fi first #define se second #define rep(i, n) for(int i=0, i##_len=(n); i<i##_len; i++) #define rep2(i, a, b) for (int i = (int)(a), i##_len=(b); i < i##_len; i++) #define rep3(i, a, b) for (int i = (int)(a), i##_len=(b); i >= i##_len; i--) #define FOR(i, a) for (auto &i: a) #define ALL(obj) begin(obj), end(obj) #define _max(x) *max_element(ALL(x)) #define _min(x) *min_element(ALL(x)) #define _sum(x) accumulate(ALL(x), 0LL) const int MOD = 1000000007; // const int MOD = 998244353; const int INF = (int)(1e13 + 7); const double EPS = 1e-8; const double PI = 3.14159265358979; template <class T> using V = vector<T>; template <class T> using VV = vector<vector<T>>; template <class T> using VVV = vector<vector<vector<T>>>; template <class T, class S> using P = pair<T, S>; template<class T> bool chmax(T &a, const T &b) {if (a < b) {a = b;return true;}return false;} template<class T> bool chmin(T &a, const T &b) {if (b < a) {a = b;return true;}return false;} int _ceil(int a, int b) { return (a >= 0 ? (a + (b - 1)) / b : (a - (b - 1)) / b); } int _mod(int a) {return a >= 0 ? a % MOD : a - (MOD * _ceil(a, MOD));} int _pow(int a, int b) {int res = 1;for (a %= MOD; b; a = a * a % MOD, b >>= 1)if (b & 1) res = res * a % MOD;return res;} struct mint {long long x;mint(long long x = 0) : x((x % MOD + MOD) % MOD) {}mint operator-() const { return mint(-x); }mint &operator+=(const mint a) {if ((x += a.x) >= MOD) x -= MOD;return *this;}mint &operator-=(const mint a) {if ((x += MOD - a.x) >= MOD) x -= MOD;return *this;}mint &operator*=(const mint a) { (x *= a.x) %= MOD;return *this; }mint operator+(const mint a) const { return mint(*this) += a; }mint operator-(const mint a) const { return mint(*this) -= a; } mint operator*(const mint a) const { return mint(*this) *= a; }mint pow(long long t) const {if (!t) return 1;mint a = pow(t >> 1);a *= a;if (t & 1) a *= *this;return a;}mint inv() const { return pow(MOD - 2); }mint &operator/=(const mint a) { return *this *= a.inv(); }mint operator/(const mint a) const { return mint(*this) /= a; }};istream &operator>>(istream &is, mint &a) { return is >> a.x; }ostream &operator<<(ostream &os, const mint &a) { return os << a.x; } // clang-format on vector<int> prime_list; void prime_factorization(int n) { prime_list = {}; while (n % 2 == 0) { n /= 2; prime_list.push_back(2); } for (int i = 3; i < (int)(sqrt((double)n)) + 2; i += 2) if (n % i == 0) while (n % i == 0) { n /= i; prime_list.push_back(i); } if (n != 1) prime_list.push_back(n); } void junkan(int n) { int m = 1; // 剰余を保持する変数(初期値1) int s = 0; // 循環節の開始位置 int t = 0; // 循環節の終了位置 V<int> ans; V<int> list(n + 10); // リストの初期化 while (true) { // mが剰余リストにある場合はループ終了 for (s = 0; list[s]; s++) if (m == list[s]) goto END; // 剰余リストになかった場合は、終端に追加 list[s] = m; // 次の剰余を計算 ans.emplace_back((m * 10) / n); m = (m * 10) % n; // 割り切れる場合はループ終了 if (m == 0) goto END; t++; } END: cout << t - s << endl; } class No1339 { public: static void solve(istream &cin, ostream &cout) { cin.tie(nullptr); cout.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); int T; cin >> T; rep(_, T) { int N; cin >> N; prime_factorization(N); rep(i, prime_list.size()) { if (prime_list[i] != 2 and prime_list[i] != 5) { break; } else if (i == prime_list.size() - 1) { cout << 1 << endl; goto label; } } junkan(N); label:; } } }; signed main() { No1339 solver; std::istream& in(std::cin); std::ostream& out(std::cout); solver.solve(in, out); return 0; }