#991371 (C++14) No.2795 Perfect Number

提出ソース

結果

問題	No.2795 Perfect Number
ユーザー	Pramod Kumar Reddy Ponnathota
提出日時	2024-06-28 21:48:57
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	6 ms / 2,000 ms
コード長	7,986 bytes
コンパイル時間	2,660 ms
コンパイル使用メモリ	200,632 KB
実行使用メモリ	11,100 KB
最終ジャッジ日時	2024-06-28 21:49:01
合計ジャッジ時間	4,022 ms
ジャッジサーバーID （参考情報）	judge4 / judge2

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	5 ms 10,904 KB
testcase_01	AC	5 ms 11,076 KB
testcase_02	AC	5 ms 11,004 KB
testcase_03	AC	5 ms 10,912 KB
testcase_04	AC	5 ms 11,056 KB
testcase_05	AC	5 ms 11,016 KB
testcase_06	AC	4 ms 11,040 KB
testcase_07	AC	5 ms 11,004 KB
testcase_08	AC	4 ms 11,016 KB
testcase_09	AC	5 ms 11,008 KB
testcase_10	AC	5 ms 11,056 KB
testcase_11	AC	5 ms 11,100 KB
testcase_12	AC	4 ms 11,076 KB
testcase_13	AC	5 ms 11,060 KB
testcase_14	AC	5 ms 10,972 KB
testcase_15	AC	5 ms 11,056 KB
testcase_16	AC	5 ms 11,080 KB
testcase_17	AC	6 ms 11,012 KB
testcase_18	AC	5 ms 10,992 KB
testcase_19	AC	6 ms 10,896 KB
testcase_20	AC	5 ms 10,908 KB
testcase_21	AC	5 ms 11,088 KB
testcase_22	AC	5 ms 11,000 KB
testcase_23	AC	5 ms 10,916 KB
testcase_24	AC	5 ms 10,940 KB
testcase_25	AC	5 ms 10,968 KB
testcase_26	AC	5 ms 10,976 KB
testcase_27	AC	5 ms 11,044 KB
testcase_28	AC	5 ms 11,048 KB
testcase_29	AC	5 ms 11,016 KB
testcase_30	AC	4 ms 10,996 KB
testcase_31	AC	5 ms 11,012 KB
testcase_32	AC	5 ms 11,084 KB
testcase_33	AC	5 ms 10,972 KB
testcase_34	AC	5 ms 10,964 KB
testcase_35	AC	5 ms 10,972 KB
testcase_36	AC	5 ms 11,000 KB
testcase_37	AC	5 ms 11,032 KB

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

ソースコード

raw source code

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using os = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T>
using oms = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define mod  1000000007
#define mod2 998244353
#define ll long long
#define bl  __int128_t
#define pb push_back
#define all(v) v.begin(),v.end()
#define bs binary_search
#define rall(v) v.rbegin(),v.rend()
#define lb lower_bound
#define ub upper_bound
#define pl pair<ll,ll>
#define f(i,n) for(ll i=0;i<n;i++)
#define inp(a,n) vector<ll> a(n); f(i,n) cin>>a[i]
#define pyes cout<<"YES\n"
#define pno cout<<"NO\n"

#pragma GCC optimize("unroll-loops")
#pragma gcc optimize("Ofast")
#pragma GCC optimization("Ofast")
#pragma optimize(Ofast)
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("popcnt")

/*void mat_mul(ll a[101][101],ll b[101][101],ll mv,ll z){
    ll mul[mv][mv];
    for (ll i=0;i<mv;i++) for(ll j=0;j<mv;j++){
            mul[i][j]=0;
            for(ll ki=0;ki<mv;ki++) mul[i][j]+=(a[i][ki]*b[ki][j])%z,mul[i][j]%=z;
    }
    for(ll i=0;i<mv;i++) for(ll j=0;j<mv;j++) a[i][j]=mul[i][j]%z; return;
}
void mat_exp(ll a[101][101],ll s[],ll l[],ll n,ll mv,ll z){
    ll m[101][101];
    for(ll i=0;i<mv;i++) for(ll j=0;j<mv;j++) m[i][j]=((s[i]*s[j])+(s[i]*l[j])+(s[j]*l[i]));
    while(n>0){
        if(n%2) mat_mul(a,m,mv,z);
        n/=2; mat_mul(m,m,mv,z);
        for(ll i=0;i<mv;i++) for(ll j=0;j<mv;j++) a[i][j]%=z,m[i][j]%=z;
    }return;
}*/

ll power(ll x,ll y,ll z=LLONG_MAX){
    ll res=1;
    while(y>0){
        if(y%2) res=(res*x)%z;
        y/=2; 
        if(y) x=(x*x)%z;
    }return res%z;
}

/*ll gcd(ll a,ll b,ll& x,ll& y){
    x=1,y=0;
    ll x1=0,y1=1,a1=a,b1=b;
    while(b1){
        ll q=a1/b1;
        tie(x,x1)=make_tuple(x1,x-q*x1);
        tie(y,y1)=make_tuple(y1,y-q*y1);
        tie(a1,b1)=make_tuple(b1,a1-q*b1);
    }return a1;
}*/

vector<ll> isP(1e3+5,1);
void setP(){
    isP[0]=isP[1]=0;
    for(ll i=2;i*i<1e3+5;i++){
        if(isP[i]==1) for(ll j=i*i;j<1e3+5;j+=i) isP[j]=0;
    }return;
}
vector<ll> pr;
void getP(){ //pr.push_back(2);
    for(ll i=3;i<1e5;i+=2) if(isP[i]) pr.push_back(i); }

#define MX 1e6
vector<ll> spf(MX+2,1);
void sieve(){
    spf[0]=0;
    for(ll i=2;i<3;i++){
        if(spf[i]==1){
            for(ll j=i;j<MX+1;j+=i) if(spf[j]==1) spf[j]=i;
        }
    }for(ll i=3;i<MX+1;i+=2){
        if(spf[i]==1){
            for(ll j=i;j<MX+1;j+=i) if(spf[j]==1) spf[j]=i;
        }
    }
    return; 
}

/*ll nCr(ll n,ll r){
    if(r>n) return 0;
    if(n-r<r) r=n-r;
    ll p=1,q=1,m;
    while(r){
        p*=n,q*=r;
        m=__gcd(p,q);
        p/=m,q/=m;
        n--,r--;
    }return p;
}*/


/*#define MX 10000
ll fac[MX+1],numInv[MX+1],facNumInv[MX+1];
void compfac(ll z){
    facNumInv[0]=facNumInv[1]=numInv[0]=numInv[1]=fac[0]=1;
    for(ll i=2;i<=MX;i++) numInv[i]=numInv[z%i]*(z-z/i)%z;
    for(ll i=2;i<=MX;i++) facNumInv[i]=(facNumInv[i-1]*numInv[i])%z;
    for(ll i=1;i<=MX;i++) fac[i]=(fac[i-1]*i)%z;
    return;
}
ll nCrmod(ll n,ll r,ll z){
    if(r>n) return 0;
    return (((fac[n]*facNumInv[r])%z)*facNumInv[n-r])%z;
}*/


/*
vector<ll> getPF(ll x){
    vector<ll> res;
    map<ll,ll> mp;
    while(x!=1){
        if(mp[spf[x]]==0) res.push_back(spf[x]);
        mp[spf[x]]++,x/=spf[x];
    }return res;
}*/


/*bool isBipc(vector<vector<ll>>& v2,ll src,vector<ll>& color){
    color[src] = 1;
    queue<ll> q;
    q.push(src);
    while (!q.empty()) {
        ll u = q.front();
        q.pop();
        for(auto z : v2[u]){
            if(color[z]==-1) color[z]=1-color[u],q.push(z);
            else if(color[z]==color[u]) return false;
        }
    }return true;
}
bool isBip(vector<vector<ll>>& v2,vector<ll>& color){
    ll n=v2.size(),i;
    for(i=1;i<=n;i++) if(color[i]==-1 && !(isBipc(v2,i,color))) return false;
    return true;
}*/


/*ll num1,num2;
template<class T, class U>
// T -> node, U->update.
struct Lsegtree{
    vector<T>st;
    vector<U>lazy;
    ll n;
    T identity_element; // related to query
    U identity_update;  // related to update
    Lsegtree(ll n, T identity_element, U identity_update)
    {
        this->n = n;
        this->identity_element = identity_element;
        this->identity_update = identity_update;
        st.assign(4*n,identity_element);
        lazy.assign(4*n, identity_update);
    }
    T combine(T l, T r)
    {
        // change this function as required.
        // related to query
        T ans = max(l,r);
        return ans;
    }
    void buildUtil(ll v, ll tl, ll tr, vector<T>&a)
    {
        if(tl == tr)
        {
            st[v]=a[tl];
            return;
        }
        ll tm = (tl + tr)/2;
        buildUtil(2*v + 1, tl, tm,a);
        buildUtil(2*v + 2,tm+1,tr,a);
        st[v] = combine(st[2*v + 1], st[2*v + 2]);
    }
    // change the following 2 functions, and you're more or less done.
    T apply(T curr, U upd, ll tl, ll tr)
    {   
        // related to update and query
        T ans = upd;
        return ans;
    }
    U combineUpdate(U old_upd, U new_upd, ll tl, ll tr)
    {   
        // related to update
        U ans = old_upd;
        ans=new_upd;
        return ans;
    }  
    void push_down(ll v, ll tl, ll tr)
    {
        if(lazy[v] == identity_update)return;
        st[v] = apply(st[v], lazy[v], tl, tr);
        if(2*v + 2 < 4*n)
        {
            ll tm = (tl + tr)>>1;
            lazy[2*v + 1] = combineUpdate(lazy[2*v+1], lazy[v], tl, tm);
            lazy[2*v + 2] = combineUpdate(lazy[2*v+2], lazy[v], tm+1,tr);            
        }
        lazy[v] = identity_update;
    }
    T queryUtil(ll v, ll tl, ll tr, ll l, ll r)
    {
        push_down(v,tl,tr);
        if(l > r)return identity_element;
        if(tr < l or tl > r)
        {
            return identity_element;
        }
        if(l <= tl and r >= tr)
        {
            return st[v];
        }
        ll tm = (tl + tr)>>1;
        return combine(queryUtil(2*v+1,tl,tm,l,r), queryUtil(2*v+2,tm+1,tr,l,r));
    }
 
    void updateUtil(ll v, ll tl, ll tr, ll l, ll r, U upd)
    {
        push_down(v,tl,tr); 
        if(tr < l or tl > r)return;
        if(tl >=l and tr <=r)
        {
            lazy[v] = combineUpdate(lazy[v],upd,tl,tr);
            push_down(v,tl,tr);
        }
        else
        {
            ll tm = (tl + tr)/2;
            updateUtil(2*v+1,tl,tm,l,r,upd);
            updateUtil(2*v+2,tm+1,tr,l,r,upd);
            st[v] = combine(st[2*v + 1], st[2*v+2]);
        }
    }
    void build(vector<T>a)
    {
        assert(a.size() == n);
        buildUtil(0,0,n-1,a);
    }
    T query(ll l, ll r)
    {
        return queryUtil(0,0,n-1,l,r);
    }
    void update(ll l,ll r, U upd)
    {
        updateUtil(0,0,n-1,l,r,upd);
    }
    ll find_ind(ll v,ll tl,ll tr,ll x){
        // have to store maximums for this to work
        if(st[v]<x) return 0;
        if(tl==tr) return tl;
        ll tm=(tl+tr)/2;
        if(st[v+v+1]>=x) return find_ind(v+v+1,tl,tm,x);
        else return find_ind(v+v+2,tm+1,tr,x-st[v+v+1]);
    }
};*/

bool isp(ll n){
    if(n<2) return 0;
    for(ll i=2;i*i<=n;i++) if(n%i==0) return 0;
    return 1;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll t=1,i,j,n,m,z=1e9+7,z2=998244353,k,x,y,q;
    //sieve(); // for SPF
    //setP();
    //getP();
    //cin>>t;
    map<ll,ll> mp,mp2,mp3;
    //compfac(z2);
    string s,s2;
    while(t--){
        cin>>n;
        set<ll> s;
        s.insert(0);
        setP();
        for(i=2;i<=31;i++){
            ll ans=1;
            if(!isp((power(2,i)-1))) continue;
            ans*=power(2,i-1);
            ans*=(power(2,i)-1);
            s.insert(ans);
        }if(s.count(n)) cout<<"Yes";
        else cout<<"No";
       // for(auto z : s) cout<<z<<endl;
    }
    return 0;
}

yukicoder

結果

テストケース

ソースコード