結果
問題 | No.1339 循環小数 |
ユーザー |
![]() |
提出日時 | 2021-01-15 22:15:20 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 17,401 bytes |
コンパイル時間 | 2,154 ms |
コンパイル使用メモリ | 204,724 KB |
最終ジャッジ日時 | 2025-01-17 19:36:37 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 3 WA * 33 |
ソースコード
/*** code generated by JHelper* More info: https://github.com/AlexeyDmitriev/JHelper* @author*/#include <bits/stdc++.h>using namespace std;using ll = long long;using ld = long double;template<typename T, typename U = T>using P = pair<T, U>;template<typename T>using V = vector<T>;using VI = vector<int>;using VL = vector<long long>;//#pragma GCC optimize("O3")//#pragma GCC target("avx2")//#pragma GCC target("avx512f")//#pragma GCC optimize("unroll-loops")//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")//#pragma GCC optimize("Ofast")#define G(size_1) vector<vector<int>>(size_1, vector<int>())#define SZ(x) ((long long)(x).size())#define READ ({long long t;cin >> t;t;})#define FOR(i, __begin, __end) for (auto i = (__begin) - ((__begin) > (__end)); i != (__end) - ((__begin) > (__end)); i += 1 - 2 * ((__begin) >(__end)))#define REP(i, __end) for (auto i = decltype(__end){0}; i < (__end); ++i)#define ALL(x) (x).begin(),(x).end()#define RALL(x) (x).rbegin(),(x).rend()#define F first#define S second#define y0 y3487465#define y1 y8687969#define j0 j1347829#define j1 j234892#define BIT(n) (1LL<<(n))#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() )#define EB emplace_back#define PB push_back#define fcout cout << fixed << setprecision(12)#define fcerr cerr << fixed << setprecision(12)#define print(x) cout << (x) << '\n'#define printE(x) cout << (x) << endl;#define fprint(x) cout << fixed << setprecision(12) << (x) << '\n'# define BYE(a) do { cout << (a) << endl; return ; } while (false)#define LB lower_bound#define UB upper_bound#define LBI(c, x) distance((c).begin(), lower_bound((c).begin(), (c).end(), (x)))#define UBI(c, x) distance((c).begin(), upper_bound((c).begin(), (c).end(), (x)))#ifdef DEBUG#define DBG(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); _err(cerr,_it, args); }#define ERR(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); _err(std::cerr,_it, args); }#else#define DBG(args...) {};#define ERR(args...) {};#endifvoid _err(std::ostream& cerr, istream_iterator<string> it){cerr << endl;}template<typename T, typename... Args>void _err(std::ostream& cerr, istream_iterator<string> it, T a, Args... args){cerr << *it << " = " << a << " ";_err(cerr, ++it, args...);}namespace aux{template<std::size_t...>struct seq{};template<std::size_t N, std::size_t... Is>struct gen_seq : gen_seq<N - 1, N - 1, Is...>{};template<std::size_t... Is>struct gen_seq<0, Is...> : seq<Is...>{};template<class Ch, class Tr, class Tuple, std::size_t... Is>void print_tuple(std::basic_ostream<Ch, Tr>& os, Tuple const& t, seq<Is...>){using swallow = int[];(void) swallow{0, (void(os << (Is == 0 ? "" : ",") << std::get<Is>(t)), 0)...};}template<class Ch, class Tr, class Tuple, std::size_t... Is>void read_tuple(std::basic_istream<Ch, Tr>& os, Tuple& t, seq<Is...>){using swallow = int[];(void) swallow{0, (void(os >> std::get<Is>(t)), 0)...};}} // aux::template<class Ch, class Tr, class... Args>auto operator<<(std::basic_ostream<Ch, Tr>& os, std::tuple<Args...> const& t)-> std::basic_ostream<Ch, Tr>&{os << "(";aux::print_tuple(os, t, aux::gen_seq<sizeof...(Args)>());return os << ")";}template<class Ch, class Tr, class... Args>auto operator>>(std::basic_istream<Ch, Tr>& os, std::tuple<Args...>& t)-> std::basic_istream<Ch, Tr>&{aux::read_tuple(os, t, aux::gen_seq<sizeof...(Args)>());return os;}template<class T>inline bool chmax(T& a, const T& b){if(a < b){a = b;return 1;}return 0;}template<class T>inline bool chmin(T& a, const T& b){if(b < a){a = b;return 1;}return 0;}template<typename T, typename U>istream& operator>>(istream& is, pair<T, U>& V){is >> V.F >> V.S;return is;}template<typename T>istream& operator>>(istream& is, vector<T>& V){for(auto&& ele : V)is >> ele;return is;}template<typename T>ostream& operator<<(ostream& os, const vector<T> V){os << "[";int cnt = 0;T curr;if(!V.empty()){for(int i = 0; i < V.size() - 1; ++i){if(V[i] == curr)cnt++;else cnt = 0;if(cnt == 4)os << "... ";if(cnt < 4)os << i << ":" << V[i] << " ";curr = V[i];}os << V.size() - 1 << ":" << V.back();}os << "]\n";return os;}template<typename T, typename U>ostream& operator<<(ostream& os, const pair<T, U> P){os << "(";os << P.first << "," << P.second;os << ")";return os;}template<typename T, typename U>ostream& operator<<(ostream& os, const set<T, U> V){os << "{";if(!V.empty()){auto it = V.begin();for(int i = 0; i < V.size() - 1; ++i){os << *it << " ";it++;}os << *it;}os << "}\n";return os;}template<typename K, typename H, typename P>ostream& operator<<(ostream& os, const unordered_set<K, H, P> V){os << "{";if(!V.empty()){auto it = V.begin();for(int i = 0; i < V.size() - 1; ++i){os << *it << " ";it++;}os << *it;}os << "}\n";return os;}template<typename K, typename C>ostream& operator<<(ostream& os, const multiset<K, C> V){os << "{";if(!V.empty()){auto it = V.begin();for(int i = 0; i < V.size() - 1; ++i){os << *it << " ";it++;}os << *it;}os << "}";return os;}template<typename K, typename T, typename C>ostream& operator<<(ostream& os, const map<K, T, C> V){os << "{";if(!V.empty()){auto it = V.begin();for(int i = 0; i < V.size() - 1; ++i){os << "(";os << it->first << "," << it->second;os << ") ";it++;}os << "(";os << it->first << "," << it->second;os << ")";}os << "}\n";return os;}template<typename K, typename T, typename C>ostream& operator<<(ostream& os, const unordered_map<K, T, C> V){os << "{";if(!V.empty()){auto it = V.begin();for(int i = 0; i < V.size() - 1; ++i){os << "(";os << it->first << "," << it->second;os << ") ";it++;}os << "(";os << it->first << "," << it->second;os << ")";}os << "}\n";return os;}template<typename T>ostream& operator<<(ostream& os, const deque<T> V){os << "[";if(!V.empty()){for(int i = 0; i < V.size() - 1; ++i){os << V[i] << "->";}if(!V.empty())os << V.back();}os << "]\n";return os;};template<typename T, typename Cont, typename Comp>ostream& operator<<(ostream& os, const priority_queue<T, Cont, Comp> V){priority_queue<T, Cont, Comp> _V = V;os << "[";if(!_V.empty()){while(_V.size() > 1){os << _V.top() << "->";_V.pop();}os << _V.top();}os << "]\n";return os;};template<class F>struct y_combinator{F f; // the lambda will be stored here// a forwarding operator():template<class... Args>decltype(auto) operator()(Args&& ... args) const{// we pass ourselves to f, then the arguments.// the lambda should take the first argument as `auto&& recurse` or similar.return f(*this, std::forward<Args>(args)...);}};// helper function that deduces the type of the lambda:template<class F>y_combinator<std::decay_t<F>> recursive(F&& f){return {std::forward<F>(f)};}struct hash_pair{template<class T1, class T2>size_t operator()(const pair<T1, T2>& p) const{auto hash1 = hash<T1>{}(p.first);auto hash2 = hash<T2>{}(p.second);return hash1^hash2;}};template<typename U>auto vec(int n, U v){return std::vector(n, v);}template<typename... Args>auto vec(int n, Args... args){auto val = vec(std::forward<Args>(args)...);return std::vector<decltype(val)>(n, std::move(val));}const double PI = 2*acos(.0);const int INF = 0x3f3f3f3f;template<class T>inline T ceil(T a, T b){return (a + b - 1)/b;}inline long long popcount(ll x){return __builtin_popcountll(x);}int64_t mod_log(int64_t a, int64_t b, int64_t p){int64_t g = 1;for(int64_t i = p; i; i /= 2) (g *= a) %= p;g = __gcd(g, p);int64_t t = 1, c = 0;for(; t%g; c++){if(t == b) return c;(t *= a) %= p;}if(b%g) return -1;t /= g;b /= g;int64_t n = p/g, h = 0, gs = 1;for(; h*h < n; h++) (gs *= a) %= n;unordered_map<int64_t, int64_t> bs;for(int64_t s = 0, e = b; s < h; bs[e] = ++s){(e *= a) %= n;}for(int64_t s = 0, e = t; s < n;){(e *= gs) %= n;s += h;if(bs.count(e)) return c + s - bs[e];}return -1;}#ifndef ATCODER_MATH_HPP#define ATCODER_MATH_HPP 1#include <algorithm>#include <cassert>#include <tuple>#include <vector>#ifndef ATCODER_INTERNAL_MATH_HPP#define ATCODER_INTERNAL_MATH_HPP 1#include <utility>namespace atcoder {namespace internal {// @param m `1 <= m`// @return x mod mconstexpr long long safe_mod(long long x, long long m) {x %= m;if (x < 0) x += m;return x;}// Fast moduler by barrett reduction// Reference: https://en.wikipedia.org/wiki/Barrett_reduction// NOTE: reconsider after Ice Lakestruct barrett {unsigned int _m;unsigned long long im;// @param m `1 <= m`barrett(unsigned int m) : _m(m), im((unsigned long long)(-1) / m + 1) {}// @return munsigned int umod() const { return _m; }// @param a `0 <= a < m`// @param b `0 <= b < m`// @return `a * b % m`unsigned int mul(unsigned int a, unsigned int b) const {// [1] m = 1// a = b = im = 0, so okay// [2] m >= 2// im = ceil(2^64 / m)// -> im * m = 2^64 + r (0 <= r < m)// let z = a*b = c*m + d (0 <= c, d < m)// a*b * im = (c*m + d) * im = c*(im*m) + d*im = c*2^64 + c*r + d*im// c*r + d*im < m * m + m * im < m * m + 2^64 + m <= 2^64 + m * (m + 1) < 2^64 * 2// ((ab * im) >> 64) == c or c + 1unsigned long long z = a;z *= b;#ifdef _MSC_VERunsigned long long x;_umul128(z, im, &x);#elseunsigned long long x =(unsigned long long)(((unsigned __int128)(z)*im) >> 64);#endifunsigned int v = (unsigned int)(z - x * _m);if (_m <= v) v += _m;return v;}};// @param n `0 <= n`// @param m `1 <= m`// @return `(x ** n) % m`constexpr long long pow_mod_constexpr(long long x, long long n, int m) {if (m == 1) return 0;unsigned int _m = (unsigned int)(m);unsigned long long r = 1;unsigned long long y = safe_mod(x, m);while (n) {if (n & 1) r = (r * y) % _m;y = (y * y) % _m;n >>= 1;}return r;}// Reference:// M. Forisek and J. Jancina,// Fast Primality Testing for Integers That Fit into a Machine Word// @param n `0 <= n`constexpr bool is_prime_constexpr(int n) {if (n <= 1) return false;if (n == 2 || n == 7 || n == 61) return true;if (n % 2 == 0) return false;long long d = n - 1;while (d % 2 == 0) d /= 2;for (long long a : {2, 7, 61}) {long long t = d;long long y = pow_mod_constexpr(a, t, n);while (t != n - 1 && y != 1 && y != n - 1) {y = y * y % n;t <<= 1;}if (y != n - 1 && t % 2 == 0) {return false;}}return true;}template <int n> constexpr bool is_prime = is_prime_constexpr(n);// @param b `1 <= b`// @return pair(g, x) s.t. g = gcd(a, b), xa = g (mod b), 0 <= x < b/gconstexpr std::pair<long long, long long> inv_gcd(long long a, long long b) {a = safe_mod(a, b);if (a == 0) return {b, 0};// Contracts:// [1] s - m0 * a = 0 (mod b)// [2] t - m1 * a = 0 (mod b)// [3] s * |m1| + t * |m0| <= blong long s = b, t = a;long long m0 = 0, m1 = 1;while (t) {long long u = s / t;s -= t * u;m0 -= m1 * u; // |m1 * u| <= |m1| * s <= b// [3]:// (s - t * u) * |m1| + t * |m0 - m1 * u|// <= s * |m1| - t * u * |m1| + t * (|m0| + |m1| * u)// = s * |m1| + t * |m0| <= bauto tmp = s;s = t;t = tmp;tmp = m0;m0 = m1;m1 = tmp;}// by [3]: |m0| <= b/g// by g != b: |m0| < b/gif (m0 < 0) m0 += b / s;return {s, m0};}// Compile time primitive root// @param m must be prime// @return primitive root (and minimum in now)constexpr int primitive_root_constexpr(int m) {if (m == 2) return 1;if (m == 167772161) return 3;if (m == 469762049) return 3;if (m == 754974721) return 11;if (m == 998244353) return 3;int divs[20] = {};divs[0] = 2;int cnt = 1;int x = (m - 1) / 2;while (x % 2 == 0) x /= 2;for (int i = 3; (long long)(i)*i <= x; i += 2) {if (x % i == 0) {divs[cnt++] = i;while (x % i == 0) {x /= i;}}}if (x > 1) {divs[cnt++] = x;}for (int g = 2;; g++) {bool ok = true;for (int i = 0; i < cnt; i++) {if (pow_mod_constexpr(g, (m - 1) / divs[i], m) == 1) {ok = false;break;}}if (ok) return g;}}template <int m> constexpr int primitive_root = primitive_root_constexpr(m);} // namespace internal} // namespace atcoder#endif // ATCODER_INTERNAL_MATH_HPPnamespace atcoder {long long pow_mod(long long x, long long n, int m) {assert(0 <= n && 1 <= m);if (m == 1) return 0;internal::barrett bt((unsigned int)(m));unsigned int r = 1, y = (unsigned int)(internal::safe_mod(x, m));while (n) {if (n & 1) r = bt.mul(r, y);y = bt.mul(y, y);n >>= 1;}return r;}long long inv_mod(long long x, long long m) {assert(1 <= m);auto z = internal::inv_gcd(x, m);assert(z.first == 1);return z.second;}// (rem, mod)std::pair<long long, long long> crt(const std::vector<long long>& r,const std::vector<long long>& m) {assert(r.size() == m.size());int n = int(r.size());// Contracts: 0 <= r0 < m0long long r0 = 0, m0 = 1;for (int i = 0; i < n; i++) {assert(1 <= m[i]);long long r1 = internal::safe_mod(r[i], m[i]), m1 = m[i];if (m0 < m1) {std::swap(r0, r1);std::swap(m0, m1);}if (m0 % m1 == 0) {if (r0 % m1 != r1) return {0, 0};continue;}// assume: m0 > m1, lcm(m0, m1) >= 2 * max(m0, m1)// (r0, m0), (r1, m1) -> (r2, m2 = lcm(m0, m1));// r2 % m0 = r0// r2 % m1 = r1// -> (r0 + x*m0) % m1 = r1// -> x*u0*g % (u1*g) = (r1 - r0) (u0*g = m0, u1*g = m1)// -> x = (r1 - r0) / g * inv(u0) (mod u1)// im = inv(u0) (mod u1) (0 <= im < u1)long long g, im;std::tie(g, im) = internal::inv_gcd(m0, m1);long long u1 = (m1 / g);// |r1 - r0| < (m0 + m1) <= lcm(m0, m1)if ((r1 - r0) % g) return {0, 0};// u1 * u1 <= m1 * m1 / g / g <= m0 * m1 / g = lcm(m0, m1)long long x = (r1 - r0) / g % u1 * im % u1;// |r0| + |m0 * x|// < m0 + m0 * (u1 - 1)// = m0 + m0 * m1 / g - m0// = lcm(m0, m1)r0 += x * m0;m0 *= u1; // -> lcm(m0, m1)if (r0 < 0) r0 += m0;}return {r0, m0};}long long floor_sum(long long n, long long m, long long a, long long b) {long long ans = 0;if (a >= m) {ans += (n - 1) * n * (a / m) / 2;a %= m;}if (b >= m) {ans += n * (b / m);b %= m;}long long y_max = (a * n + b) / m, x_max = (y_max * m - b);if (y_max == 0) return ans;ans += (n - (x_max + a - 1) / a) * y_max;ans += floor_sum(y_max, a, m, (a - x_max % a) % a);return ans;}} // namespace atcoder#endif // ATCODER_MATH_HPPusing namespace atcoder;void solve(std::istream& cin, std::ostream& cout, std::ostream& cerr){auto solve = [&](){ll N;cin >> N;N = N/gcd(10,N);ll g = gcd(10, N);// ll t = atcoder::inv_mod(10/gcd(10,N), N/gcd(10,N));if(ll x = mod_log(10/g, inv_mod(10/g, N), N);x)print(x + 1);elseprint(1);};int testcases;cin >> testcases;for(int case_num = 1; case_num <= testcases; case_num++){solve();}}#undef intint main() {istream& in(cin);ostream& out(cout);ostringstream err;in.tie(0); ios::sync_with_stdio(0);solve(in, out, err);return 0;}