#917856 (C++17) No.577 Prime Powerful Numbers

提出ソース

結果

問題	No.577 Prime Powerful Numbers
ユーザー	Katu2ou
提出日時	2023-10-04 23:00:12
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	96 ms / 2,000 ms
コード長	5,771 bytes
コンパイル時間	4,074 ms
コンパイル使用メモリ	247,296 KB
実行使用メモリ	5,376 KB
最終ジャッジ日時	2024-07-26 14:54:33
合計ジャッジ時間	4,985 ms
ジャッジサーバーID （参考情報）	judge5 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	5 ms 5,376 KB
testcase_02	AC	4 ms 5,376 KB
testcase_03	AC	46 ms 5,376 KB
testcase_04	AC	9 ms 5,376 KB
testcase_05	AC	68 ms 5,376 KB
testcase_06	AC	96 ms 5,376 KB
testcase_07	AC	72 ms 5,376 KB
testcase_08	AC	43 ms 5,376 KB
testcase_09	AC	27 ms 5,376 KB
testcase_10	AC	2 ms 5,376 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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 };

ll Modpow(__int128_t a, ll n, ll mo) {
	__int128_t r=1;
	a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

bool Mirror_Rebin(ll n){
    if(n == 2) return true;
    if(n % 2 == 0) 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 = Modpow(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 = Modpow(val,(ll)2,n);
        }
        if(!fin) return false;
    }
    return true;
} 


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);
  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=40;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;
}

yukicoder

結果

テストケース

ソースコード