結果
問題 |
No.3236 累乗数大好きbot
|
ユーザー |
![]() |
提出日時 | 2025-08-15 22:17:02 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3,696 ms / 4,000 ms |
コード長 | 6,736 bytes |
コンパイル時間 | 2,118 ms |
コンパイル使用メモリ | 211,772 KB |
実行使用メモリ | 9,068 KB |
最終ジャッジ日時 | 2025-08-15 22:18:30 |
合計ジャッジ時間 | 55,608 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge6 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 31 |
ソースコード
/* Original Python code (kept at the beginning as required) from collections import defaultdict def gcd(a, b): while a: a, b = b%a, a return b def is_prime(n): if n == 2: return 1 if n == 1 or n%2 == 0: return 0 m = n - 1 lsb = m & -m s = lsb.bit_length()-1 d = m // lsb test_numbers = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37] for a in test_numbers: if a == n: continue x = pow(a,d,n) r = 0 if x == 1: continue while x != m: x = pow(x,2,n) r += 1 if x == 1 or r == s: return 0 return 1 def find_prime_factor(n): if n%2 == 0: return 2 m = int(n**0.125)+1 for c in range(1,n): f = lambda a: (pow(a,2,n)+c)%n y = 0 g = q = r = 1 k = 0 while g == 1: x = y while k < 3*r//4: y = f(y) k += 1 while k < r and g == 1: ys = y for _ in range(min(m, r-k)): y = f(y) q = q*abs(x-y)%n g = gcd(q,n) k += m k = r r *= 2 if g == n: g = 1 y = ys while g == 1: y = f(y) g = gcd(abs(x-y),n) if g == n: continue if is_prime(g): return g elif is_prime(n//g): return n//g else: return find_prime_factor(g) def factorize(n): res = {} while not is_prime(n) and n > 1: # nが合成数である間nの素因数の探索を繰り返す p = find_prime_factor(n) s = 0 while n%p == 0: # nが素因数pで割れる間割り続け、出力に追加 n //= p s += 1 res[p] = s if n > 1: # n>1であればnは素数なので出力に追加 res[n] = 1 return res ans = [] Q = int(input()) for _ in range(Q): N = int(input()) a = set(factorize(N).values()) for i in range(60,0,-1): if(all([x%i == 0 for x in a])): ans.append(str(i)) break print("\n".join(ans)) */ #include <bits/stdc++.h> using namespace std; using u64 = unsigned long long; using u128 = __uint128_t; using i128 = __int128_t; u64 gcd_u64(u64 a, u64 b){ while(a){ u64 t = b % a; b = a; a = t; } return b; } u64 mul_mod(u64 a, u64 b, u64 mod){ return (u128)a * b % mod; } u64 pow_mod(u64 a, u64 e, u64 mod){ u128 res = 1; u128 base = a % mod; while(e){ if(e & 1) res = (res * base) % mod; base = (base * base) % mod; e >>= 1; } return (u64)res; } // Miller-Rabin primality test (keeps same small-base list as Python version) bool is_prime(u64 n){ if(n == 2) return true; if(n < 2 || (n % 2 == 0)) return false; u64 m = n - 1; u64 lsb = m & (~m + 1); // m & -m int s = 0; u64 tmp = lsb; while(tmp > 1){ tmp >>= 1; ++s; } // s = lsb.bit_length() - 1 in python if(lsb == 1) s = 0; // compute d = m // lsb u64 d = m / lsb; const u64 test_numbers_arr[] = {2ULL,3ULL,5ULL,7ULL,11ULL,13ULL,17ULL,19ULL,23ULL,29ULL,31ULL,37ULL}; for(u64 a : test_numbers_arr){ if(a == n) continue; u64 x = pow_mod(a, d, n); int r = 0; if(x == 1) continue; while(x != m){ x = mul_mod(x, x, n); r += 1; if(x == 1 || r == s) return false; } } return true; } // Pollard-Brent style factor finder translated from the Python code u64 find_prime_factor(u64 n){ if(n % 2 == 0) return 2; // m = int(n**0.125) + 1 // compute integer floor of n^(1/8) long double nd = (long double)n; u64 m = (u64)floor(powl(nd, 1.0L/8.0L)) + 1; for(u64 c = 1; ; ++c){ auto f = [&](u64 a)->u64{ u64 t = mul_mod(a, a, n); t += c; if(t >= n) t -= n; return t; }; u64 y = 0; u64 g = 1; u64 q = 1; u64 r = 1; u64 k = 0; u64 x = 0; u64 ys = 0; while(g == 1){ x = y; while(k < (3 * r) / 4){ y = f(y); ++k; } while(k < r && g == 1){ ys = y; u64 limit = (m < (r - k) ? m : (r - k)); for(u64 i = 0; i < limit; ++i){ y = f(y); u64 diff = (x > y) ? (x - y) : (y - x); if(diff == 0) diff = n; // to avoid q becoming 0 in intermediate step q = (u128)q * diff % n; } g = gcd_u64(q, n); k += m; } if(g == 0) g = 1; if(k >= r){ k = r; r <<= 1; } } if(g == n){ g = 1; y = ys; while(g == 1){ y = f(y); u64 diff = (x > y) ? (x - y) : (y - x); g = gcd_u64(diff, n); } } if(g == n) continue; if(is_prime(g)) return g; if(is_prime(n / g)) return n / g; return find_prime_factor(g); } // unreachable return 1; } unordered_map<u64,int> factorize(u64 n){ unordered_map<u64,int> res; if(n <= 1) return res; while(n > 1 && !is_prime(n)){ u64 p = find_prime_factor(n); int s = 0; while(n % p == 0){ n /= p; ++s; } res[p] += s; } if(n > 1){ res[n] += 1; } return res; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int Q; if(!(cin >> Q)) return 0; vector<string> answers; for(int _ = 0; _ < Q; ++_){ u64 N; cin >> N; auto mp = factorize(N); set<int> exps; for(auto &kv : mp) exps.insert(kv.second); // replicate Python behavior: for empty set, all(...) is True, so it will pick 60 int found = 1; for(int i = 60; i >= 1; --i){ bool ok = true; for(int x : exps){ if(x % i != 0){ ok = false; break; } } if(ok){ answers.push_back(to_string(i)); found = 1; break; } } // (always found because loop includes i=1) } for(size_t i = 0; i < answers.size(); ++i){ if(i) cout << '\n'; cout << answers[i]; } cout << '\n'; return 0; }