結果
問題 | No.1339 循環小数 |
ユーザー |
|
提出日時 | 2021-01-15 21:43:53 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 26 ms / 2,000 ms |
コード長 | 1,438 bytes |
コンパイル時間 | 3,569 ms |
コンパイル使用メモリ | 135,844 KB |
最終ジャッジ日時 | 2025-01-17 18:54:23 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 36 |
ソースコード
#include <iostream>#include <algorithm>#include <map>#include <set>#include <queue>#include <stack>#include <numeric>#include <bitset>#include <cmath>static const int MOD = 1000000007;using ll = long long;using u32 = unsigned;using u64 = unsigned long long;using namespace std;template<class T> constexpr T INF = ::numeric_limits<T>::max() / 32 * 15 + 208;template <class T>T pow_ (T x, T n, T M){uint64_t u = 1, xx = x;while (n > 0){if (n&1) u = u * xx % M;xx = xx * xx % M;n >>= 1;}return static_cast<T>(u);};template<class T>vector<T> divisor(T n){vector<T> ret;for(T i = 1; i * i <= n; i++) {if(n % i == 0) {ret.push_back(i);if(i * i != n) ret.push_back(n / i);}}sort(begin(ret), end(ret));return(ret);}void solve(){int x;cin >> x;while(x%2 == 0) x /= 2;while(x%5 == 0) x /= 5;if(x == 1) {puts("1");return;}int phi = x, xx = x;for (int i = 2; i * i <= x; ++i) {if (xx % i == 0) {phi -= phi / i;while(xx % i == 0) xx /= i;}}if(xx > 1) phi -= phi/xx;for (auto &&i : divisor(phi)) {if(pow_(10, i, x) == 1){cout << i << "\n";return;}}}int main() {int t;cin >> t;while(t--){solve();}return 0;}