結果
| 問題 | No.577 Prime Powerful Numbers |
| ユーザー |
 Katu2ou
|
| 提出日時 | 2023-10-04 20:09:59 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 8,838 bytes |
| コンパイル時間 | 4,166 ms |
| コンパイル使用メモリ | 233,864 KB |
| 実行使用メモリ | 10,624 KB |
| 最終ジャッジ日時 | 2024-07-26 14:51:50 |
| 合計ジャッジ時間 | 10,373 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 19 ms
10,624 KB |
| testcase_01 | AC | 155 ms
5,248 KB |
| testcase_02 | AC | 5 ms
5,376 KB |
| testcase_03 | TLE | - |
| testcase_04 | AC | 73 ms
5,376 KB |
| testcase_05 | TLE | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
ソースコード
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
#define rep2(i, m, n) for (int i = (m); i < (n); ++i)
#define rep(i, n) rep2(i, 0, n)
#define drep2(i, m, n) for (int i = (m)-1; i >= (n); --i)
#define drep(i, n) drep2(i, n, 0)
#define all(...) std::begin(__VA_ARGS__), std::end(__VA_ARGS__)
#define rall(...) std::rbegin(__VA_ARGS__), std::rend(__VA_ARGS__)
#define FOR(i, a, b) for (int i = (a), i##_len = (b); i <= i##_len; ++i)
#define REV(i, a, b) for (int i = (a); i >= (b); --i)
#define CLR(a, b) memset((a), (b), sizeof(a))
#define DUMP(x) cout << #x << " = " << (x) << endl;
#define INF 1001001001001001001ll
#define inf (int)1001001000
#define MOD 998244353
#define Dval 1e-12
#define fcout cout << fixed << setprecision(12)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
using ll = long long;
using vi = vector<int>;
using vl = vector<long long>;
using vs = vector<string>;
using vd = vector<double>;
using vc = vector<char>;
using vb = vector<bool>;
using vpii = vector<pair<int, int>>;
using vpll = vector<pair<long long, long long>>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<long long>>;
using vvd = vector<vector<double>>;
using vvc = vector<vector<char>>;
using vvb = vector<vector<bool>>;
using vvvi = vector<vector<vector<int>>>;
using pii = pair<int, int>;
using pll = pair<long long, long long>;
using mint = atcoder::modint998244353;
ll POW(ll x, ll n){ll ret=1; while(n>0){ if(n&1) ret=ret*x; x=x*x; n>>=1; } return ret;}
ll modpow(ll a, ll n, ll p) { if(n==0) return (ll)1; if (n == 1) return a % p; if (n % 2 == 1) return (a * modpow(a, n - 1, p)) % p; ll t = modpow(a, n / 2, p); return (t * t) % p;}
ll modinv(ll a, ll m) { if(m==0)return (ll)1; ll b = m, u = 1, v = 0; while (b) { ll t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); } u %= m; if (u < 0) u += m; return u;}
const int MAXCOMB=510000;
ll MODCOMB = 998244353;
ll fac[MAXCOMB], finv[MAXCOMB], inv[MAXCOMB];
void COMinit() { fac[0] = fac[1] = 1; finv[0] = finv[1] = 1; inv[1] = 1; for (int i = 2; i < MAXCOMB; i++) { fac[i] = fac[i - 1] * i % MODCOMB; inv[i] = MODCOMB - inv[MODCOMB%i] * (MODCOMB / i) % MODCOMB; finv[i] = finv[i - 1] * inv[i] % MODCOMB; }}
ll COM(ll n, ll k) { if (n < k) return 0; if (n < 0 || k < 0) return 0; return fac[n] * (finv[k] * finv[n - k] % MODCOMB) % MODCOMB;}
ll com(ll n,ll m){ if(n<m || n<=0 ||m<0){ return 0; } if( m==0 || n==m){ return 1; } ll k=1; for(ll i=1;i<=m;i++){ k*=(n-i+1); k%=MODCOMB; k*=modinv(i,MODCOMB); k%=MODCOMB; } return k;}
ll rad(ll u, ll p){ ll cnt=0; while(u%p==0){ u/=p; cnt++; } return cnt;}
template <typename T> inline bool chmax(T &a, T b) { return ((a < b) ? (a = b, true) : (false));}
template <typename T> inline bool chmin(T &a, T b) { return ((a > b) ? (a = b, true) : (false));}
void fail() { cout << "-1\n"; exit(0); } void no() { cout << "No\n"; exit(0); } void yes() { cout << "Yes\n"; exit(0); }
template<class T> void er(T a) { cout << a << '\n'; exit(0); }
int dx[] = { 1,0,-1,0,1,1,-1,-1,0 }; int dy[] = { 0,1,0,-1,1,-1,1,-1,0 };
long long SQUARE_MOD(ll n, ll m){
if(n == 0) return 0;
ll sum = 0;
ll mul = n;
ll pow9 = 0;
while(mul > 0){
ll val = 0;
val = n * (mul % 9);
val %= m;
for(int i = 0; i < pow9; i++){
val *= 9;
val %= m;
}
sum += val;
sum %= m;
mul /= 9;
pow9++;
}
return sum;
}
//intを超えた2数のmod積の計算(n,m <= 10^18)
long long MULTIPLY(ll n, ll m, ll mod){
if(n == 0 || m == 0) return 0;
ll sum = 0;
ll mul = m;
ll pow9 = 0;
while(mul > 0){
ll val = 0;
val = n * (mul % 9);
val %= mod;
for(int i = 0; i < pow9; i++){
val *= 9;
val %= mod;
}
sum += val;
sum %= mod;
mul /= 9;
pow9++;
}
return sum;
}
long long POW_MOD(ll a, ll n, ll m){
if(n == 0) return 1;
if(a == 0) return 0;
ll sum = 1;
ll val = a;
while(n > 0){
if(n & 1){
sum = MULTIPLY(sum, val, m);
}
val = SQUARE_MOD(val, m);
n >>= 1;
}
return sum;
}
bool Mirror_Rebin(ll n){
if(n == 2) return true;
if(n % 2 == 0 || n == 1) return false;
bool comp = false;
ll m = n;
m--;
ll rad = 0;
while(m % 2 == 0){
rad++;
m /= 2;
}
//vector<ll> vec = {2, 13, 23, 1662803}; //nがintの範囲ならこれで十分
vector<ll> vec = {2,3,5,7,11,13,17,19,23,29,31,37}; //nが64bit用
for(auto g: vec){
if(n == g) return true;
}
for(int i = 0; i < vec.size(); i++){
ll a = vec[i];
ll val = POW_MOD(a,m,n);
if(val == 1) continue;
bool fin = false;
for(int j = 0; j < rad; j++){
if(val == n-1){
fin = true;
continue;
}
val = POW_MOD(val,2,n);
}
if(!fin) return false;
}
return true;
}
ll GCD(ll a, ll b){
if(a%b == 0){
return b;
}else{
return GCD(b, a%b);
}
}
long long random_uniform(long long n) {
random_device rnd;
mt19937_64 mt(rnd());
uniform_int_distribution<long long> dist(0, n); //[0,n]の一様分布から生成
return dist(mt);
}
vector<pair<ll, ll>> Fast_Factrization(ll n){
vector<pair<ll, ll>> prime;
vector<ll> small_prime = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};
for(auto g: small_prime){
if(n % g == 0){
ll cnt = 0;
while(n % g == 0){
n /= g;
cnt++;
}
prime.push_back(make_pair(g,cnt));
}
}
while(true){
if(n == 1) return prime;
if(Mirror_Rebin(n)){
prime.push_back(make_pair(n,1));
return prime;
}
for(ll c = 1; c < n; c++){ //ρ法の部分
ll y = random_uniform(n-1);
ll r = 1;
ll k = 0;
ll x = y;
int fin = 0;
while(true){
while(k < r){
k = k + 1;
y = (SQUARE_MOD(y, n) + c) % n;
ll g = GCD(abs(x-y), n);
if(g != 1){
if(Mirror_Rebin(g)){
fin = 1;
ll cnt = 0;
while(n % g == 0){
cnt++;
n /= g;
}
prime.push_back(make_pair(g,cnt));
}
else fin = 2;
break;
}
}
if(fin != 0) break;
r = 2*r;
x = y;
}
if(fin == 2) continue;
if(fin == 1) break;
}
}
}
ll proot(ll n, ll m){
if(m == 1)return n;
ll root = (ll)round(pow(n, 1.0/m));
if((ll)POW(root, m) == n) return root;
else return -1;
}
int main(){
cin.tie(nullptr);
ios::sync_with_stdio(false);
/* vpll v =Fast_Factrization(701589870330694941);
for(auto g: v){
cout<<g.fi<<" "<<g.se<<endl;
}*/
int q;
cin>>q;
while(q--){
ll n;
cin>>n;
if(n<=3){
cout<<"No"<<endl;
continue;
}
if(n%2==0){
cout<<"Yes"<<endl;
continue;
}
ll pow2=2;
ll yes = 0;
while(n-pow2>=2){
ll m=n-pow2;
if(m==1)break;
for(ll i=64;i>=1;i--){
ll r=proot(m,i);
if(r==-1)continue;
if(r==1)continue;
if(Mirror_Rebin(r)) yes=1;
break;
}
pow2*=2;
}
if(yes == 1)cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
return 0;
}