結果
問題 | No.577 Prime Powerful Numbers |
ユーザー | はまやんはまやん |
提出日時 | 2017-10-14 14:02:16 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 4,882 bytes |
コンパイル時間 | 1,377 ms |
コンパイル使用メモリ | 172,496 KB |
実行使用メモリ | 13,640 KB |
最終ジャッジ日時 | 2024-11-17 18:36:10 |
合計ジャッジ時間 | 20,623 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 290 ms
13,636 KB |
testcase_01 | AC | 1,078 ms
10,020 KB |
testcase_02 | AC | 142 ms
13,636 KB |
testcase_03 | TLE | - |
testcase_04 | AC | 1,110 ms
13,640 KB |
testcase_05 | TLE | - |
testcase_06 | AC | 838 ms
10,016 KB |
testcase_07 | TLE | - |
testcase_08 | TLE | - |
testcase_09 | TLE | - |
testcase_10 | AC | 18 ms
10,020 KB |
ソースコード
#include<bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<b;i++) #define rrep(i,a,b) for(int i=a;i>=b;i--) #define fore(i,a) for(auto &i:a) #pragma GCC optimize ("-O3") using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); } //--------------------------------------------------------------------------------------------------- #ifdef _MSC_VER #pragma push_macro("long") #undef long #ifdef _WIN32 inline unsigned int __builtin_ctz(unsigned int x) { unsigned long r; _BitScanForward(&r, x); return r; } inline unsigned int __builtin_clz(unsigned int x) { unsigned long r; _BitScanReverse(&r, x); return 31 - r; } inline unsigned int __builtin_ffs(unsigned int x) { unsigned long r; return _BitScanForward(&r, x) ? r + 1 : 0; } inline unsigned int __builtin_popcount(unsigned int x) { return __popcnt(x); } inline unsigned int hidword(unsigned long long x) { return static_cast<unsigned int>(x >> 32); } inline unsigned int lodword(unsigned long long x) { return static_cast<unsigned int>(x & 0xFFFFFFFF); } inline unsigned long long __builtin_ctzll(unsigned long long x) { return lodword(x) ? __builtin_ctz(lodword(x)) : __builtin_ctz(hidword(x)) + 32; } inline unsigned long long __builtin_clzll(unsigned long long x) { return hidword(x) ? __builtin_clz(hidword(x)) : __builtin_clz(lodword(x)) + 32; } inline unsigned long long __builtin_ffsll(unsigned long long x) { return lodword(x) ? __builtin_ffs(lodword(x)) : hidword(x) ? __builtin_ffs(hidword(x)) + 32 : 0; } inline unsigned long long __builtin_popcountll(unsigned long long x) { return __builtin_popcount(lodword(x)) + __builtin_popcount(hidword(x)); } #endif // _WIN32 #pragma pop_macro("long") #endif // _MSC_VER typedef long long ll; typedef __int128 int128_t; //typedef ll int128_t; int128_t powmod(int128_t x, int128_t y, int128_t p) { // O(log y) assert(0 <= x and x < p); assert(0 <= y); int128_t z = 1; for (int128_t i = 1; i <= y; i <<= 1) { if (y & i) z = z * x % p; x = x * x % p; } return z; } int K = 30; int init = 0; std::random_device rd; std::mt19937_64 eng; std::uniform_int_distribution<unsigned long long> distr; ll getrandll(ll l, ll r) { // [l,r] if (!init) { eng.seed(rd()); init = 1; } return distr(eng) % (r - l + 1) + l; } bool isprime(ll n) { if (n == 2) return true; if (n == 1 || n % 2 == 0) return false; const ll d = (n - 1) >> __builtin_ctzll(n - 1); rep(_, 0, K) { ll a = getrandll(1, n - 2); int128_t t = d; int128_t y = powmod(a, t, n); while (t != n - 1 and y != 1 and y != n - 1) { y = y * y % n; t *= 2; } if (y != n - 1 and t % 2 == 0) return false; } return true; } /*--------------------------------------------------------------------------------------------------- ∧_∧ ∧_∧ (´<_` ) Welcome to My Coding Space! ( ´_ゝ`) / ⌒i / \ | | / / ̄ ̄ ̄ ̄/ | __(__ニつ/ _/ .| .|____ \/____/ (u ⊃ ---------------------------------------------------------------------------------------------------*/ typedef long long ll; typedef long double ld; #define INF 1LL<<60 ld lginf = -1; ll mul(ll a, ll b) { if (lginf < 0) lginf = log10l(INF); ld aa = log10l(a), bb = log10l(b); if (lginf <= aa + bb) return INF; return a * b; } ll gcd(ll a, ll b) { return a ? gcd(b%a, a) : b; } ll lcm(ll a, ll b) { if (a == INF || b == INF) return INF; return mul(a / gcd(a, b), b); } ll fastpow(ll x, ll n) { ll ret = 1; while (0 < n) { if ((n % 2) == 0) x = mul(x,x), n >>= 1; else ret = mul(ret,x), --n; } return ret; } ll N; #define INF 1LL<<60 #define yes "Yes" #define no "No" //--------------------------------------------------------------------------------------------------- int isprimeFact(ll n) { rep(k, 1, 65) { ll ng = 0, ok = INF; while (ng + 1 != ok) { ll x = (ng + ok) / 2; if (n <= fastpow(x, k)) ok = x; else ng = x; } if (fastpow(ok, k) == n) { if (isprime(ok)) return 1; } } return 0; } //--------------------------------------------------------------------------------------------------- string solve() { cin >> N; if (N % 2 == 0) { if (4 <= N) return yes; else return no; } for (int128_t q = 2; q < N; q *= 2) if (isprimeFact(N - q)) return yes; return no; } //--------------------------------------------------------------------------------------------------- void _main() { int Q; cin >> Q; rep(q, 0, Q) cout << solve() << endl; }