結果

問題 No.2929 Miracle Branch
ユーザー nouka28
提出日時 2024-09-07 11:25:05
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 301 ms / 2,000 ms
コード長 10,033 bytes
コンパイル時間 6,438 ms
コンパイル使用メモリ 335,100 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-07 11:25:24
合計ジャッジ時間 18,019 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 43
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include<bits/stdc++.h>
using namespace std;
#include<atcoder/all>
using namespace atcoder;
#define int long long
//math
namespace nouka28{
    random_device rnd; 
    mt19937 mt(rnd());
    const long long MT_MAX=(1LL<<62)-1;
    uniform_int_distribution<long long> rd(0,MT_MAX);
    double randd(){
        return 1.0*rd(mt)/MT_MAX;
    }
    long long randint(long long a,long long b){
        // [a,b]の乱数を生成
        return a+rd(mt)%(b-a+1);
    }
    template<class T=long long>
    vector<T> Quotients(T n){
        vector<T> retl,retr;
        for(int i=1;i*i<=n;i++){
            retl.push_back(i);
            if(i<n/i)retr.push_back(n/i);
        }
        reverse(retr.begin(),retr.end());
        retl.insert(retl.end(),retr.begin(),retr.end());
        return retl;
    }
    template<class T=long long>T ceil_sqrt(T n){
        T l=-1,r=n;
        while(r-l>1){
            T m=(l+r)>>1;
            if(m*m>=n)r=m;
            else l=m;
        }
        return r;
    }
    //ceil(a/b)
    template<class T=long long>T ceil(T a,T b){
        if(a>=0){
            return (a+b-1)/b;
        }else{
            return (a)/b;
        }
    };
    //floor(a/b)
    template<class T=long long>T floor(T a,T b){
        if(a>=0){
        return a/b;
        }else{
            return -(-a+b-1)/b;
        }
    };
    //x^y mod m
    template<class T=long long>T modpow(T x,T y,T m){
        T res=1%m;x%=m;
        while(y){
            if(y%2)res=(res*x)%m;
            x=(x*x)%m;
            y>>=1;
        }
        return res;
    }
    //a^0+a^1+..+a^(n-1) (mod m)
    template<class T>
    T geometric_progression(T a,T n,T m){
        if(n==0)return 0;
        if(n%2==1){
            return (geometric_progression(a,n-1,m)*a+1)%m;
        }else{
            return (geometric_progression(a*a%m,n/2,m)*(1+a))%m;
        }
    };
    //素数判定(高速)
    bool is_prime(long long n){
        if(n<=1)return 0;
        if(n==2)return 1;
        if(n%2==0)return 0;
        long long s=0,d=n-1;
        while(d%2==0)d/=2,s++;
        if(n<4759123141LL){
            for(long long e:{2,7,61}){
                if(n<=e)break;
                long long t,x=modpow<__int128_t>(e,d,n);
                if(x!=1){
                    for(t=0;t<s;t++){
                        if(x==n-1)break;
                        x=__int128_t(x)*x%n;
                    }
                    if(t==s)return 0;
                }
            }
            return 1;
        }else{
            for(long long e:{2,325,9375,28178,450775,9780504,1795265022}){
                if(n<=e)break;
                long long t,x=modpow<__int128_t>(e,d,n);
                if(x!=1){
                    for(t=0;t<s;t++){
                        if(x==n-1)break;
                        x=__int128_t(x)*x%n;
                    }
                    if(t==s)return 0;
                }
            }
            return 1;   
        }
    }
    //Xor Shift
    unsigned xor_shift_rng(){
        static unsigned tx=123456789,ty=362436069,tz=521288629,tw=88675123;
        unsigned tt=(tx^(tx<<11));
        tx=ty,ty=tz,tz=tw;
        return (tw=(tw^(tw>>19))^(tt^(tt>>8)));
    }
    //ロー法 Nを割り切る素数を見つける
    long long pollard(long long n){
        if(n%2==0)return 2;
        if(is_prime(n))return n;
        long long step=0;
        while(true){
            long long r=(long long)xor_shift_rng();
            auto f=[&](long long x)->long long {return ((__int128_t(x)*x)%n+r)%n;};
            long long x=++step,y=f(x);
            while(true){
                long long p=gcd(abs(y-x),n);
                if(p==0||p==n)break;
                if(p!=1)return p;
                x=f(x);
                y=f(f(y));
            }
        }
    }
    //internal fast factrize vector
    void _internal_factrize_vector(long long n,vector<long long>&v){
        if(n==1)return;
        long long p=pollard(n);
        if(p==n){v.push_back(p);return;}
        _internal_factrize_vector(p,v);
        _internal_factrize_vector(n/p,v);
    }
    //fast factrize vector
    vector<long long> factrize_vector(long long n){
        vector<long long> res;
        _internal_factrize_vector(n,res);
        sort(res.begin(),res.end());
        return res;
    }
    //internal fast factrize map
    void _internal_factrize_map(long long n,map<long long,long long>&v){
        if(n==1)return;
        long long p=pollard(n);
        if(p==n){v[p]++;return;}
        _internal_factrize_map(p,v);
        _internal_factrize_map(n/p,v);
    }
    //fast factrize map
    map<long long,long long> factrize_map(long long n){
        map<long long,long long> res;
        _internal_factrize_map(n,res);
        return res;
    }
    //fast factor
    vector<long long> factor(long long n){
        map<long long,long long> fm;_internal_factrize_map(n,fm);
        vector<long long> res={1};
        for(auto[i,j]:fm){
            vector<long long> tmp;
            int p=1;
            for(long long k=0;k<=j;k++){
                for(auto e:res){
                    tmp.push_back(e*p);
                }
                p*=i;
            }
            swap(res,tmp);
        }
        return res;
    }
    //euler phi function
    long long euler_phi(long long n){
        vector<long long> ps=factrize_vector(n);
        ps.erase(unique(ps.begin(),ps.end()),ps.end());
        for(long long p:ps){
            n/=p;n*=(p-1);
        }
        return n;
    }
    //ax+by=gcd(a,b)
    template<class T=long long>
    tuple<T,T,T> extgcd(T a,T b){
        T x1=1,y1=0,d1=a,x2=0,y2=1,d2=b;
        while(d2!=0){
            T q=d1/d2,u=d1-d2*q,v=x1-x2*q,w=y1-y2*q;
            d1=d2;d2=u;x1=x2;x2=v;y1=y2;y2=w;
        }
        if(d1<0){
            d1=-d1;x1=-x1;y1=-y1;
        }
        return {d1,x1,y1};
    }
    //x inverse (mod m)
    long long modinv(long long a,long long m){
        long long b=m,u=1,v=0;
        while(b){
            long long t=a/b;
            a-=t*b;swap(a,b);
            u-=t*v;swap(u,v);
        }
        u%=m;
        if(u<0)u+=m;
        return u;
    }
    //find primitive root
    long long primitive_root(long long p){
        vector<long long> f=factrize_vector(p-1);
        f.erase(unique(f.begin(),f.end()),f.end());
        while(1){
            long long x=randint(1,p-1);
            bool flg=1;
            for(auto e:f)if(modpow<__int128_t>(x,(p-1)/e,p)==1){flg=0;break;}
            if(flg)return x;
        }
    }
    //x^k=y (mod m) gcd(x,m)=1 k>=0
    long long discrete_logarithm_coprime_mod(long long x,long long y,long long m){
        x%=m;y%=m;
        if(y==1||m==1){
            return 0;
        }
        if(x==0){
            if(y==0)return 1;
            else return -1;
        }
        long long M=ceil_sqrt(m),a=modpow(modinv(x,m),M,m);
        unordered_map<long long,long long> mp;
        long long pow_x=1;
        for(long long i=0;i<M;i++){
            if(!mp.count(pow_x))mp[pow_x]=i;
            pow_x=pow_x*x%m;
        }
        long long ya=y;
        for(long long i=0;i<M;i++){
            if(mp.count(ya))return M*i+mp[ya];
            ya=ya*a%m;
        }
        return -1;
    }
    //x^k=y (mod m) gcd(x,m)=1 k>=1
    long long discrete_Nlogarithm_coprime_mod(long long x,long long y,long long m){
        if(m==1){
            if(x==1)return 1;
            else return -1;
        }
        if(x==0){
            if(y==0)return 1;
            else return -1;
        }
        long long M=ceil_sqrt(m),a=modpow(modinv(x,m),M,m);
        unordered_map<long long,long long> mp;
        long long pow_x=1;
        for(long long i=0;i<=M;i++){
            if(!mp.count(pow_x))mp[pow_x]=i;
            pow_x=pow_x*x%m;
        }
        long long ya=y;
        for(long long i=0;i<M;i++){
            if(ya==1&&i>0)return i*M;
            else if(mp.count(ya))return M*i+mp[ya];
            ya=ya*a%m;
        }
        return -1;
    }
    //x^k=y (mod m) k>=0
    long long discrete_logarithm_arbitrary_mod(long long x,long long y,long long m){
        if(m==1){
            return 0;
        }
        x%=m;y%=m;
        long long d,pow_x=1;
        for(d=0;;d++){
            if(!(m>>d))break;
            if(pow_x==y){
                return d;
            }
            pow_x=pow_x*x%m;
        }
        long long g=gcd(pow_x,m);
        if(y%g!=0){
            return -1;
        }
        m/=g;
        long long z=y*modinv(pow_x,m),t=discrete_logarithm_coprime_mod(x,z,m);
        if(t==-1)return -1;
        else return d+t;
    }
    //x^k=y (mod m) k>=1
    long long discrete_Nlogarithm_arbitrary_mod(long long x,long long y,long long m){
        if(m==1){
            if(x==1)return 1;
            else return -1;
        }
        x%=m;y%=m;
        long long d,pow_x=1;
        for(d=0;;d++){
            if(!(m>>d))break;
            if(pow_x==y&&d){
                return d;
            }
            pow_x=pow_x*x%m;
        }
        long long g=gcd(pow_x,m);
        if(y%g!=0){
            return -1;
        }
        m/=g;
        long long z=y*modinv(pow_x,m),t;
        if(d)t=discrete_logarithm_coprime_mod(x,z,m);
        else t=discrete_Nlogarithm_coprime_mod(x,y,m);
        if(t==-1)return -1;
        else return d+t;
    }
}
signed main(){
    int n;cin>>n;
    if(n==1){
        cout<<2<<endl;
        cout<<1<<" "<<2<<endl;
        cout<<"b g"<<endl;
    }
    auto v=nouka28::factrize_map(n);
    vector<pair<int,int>> vec;
    int sum=0;
    for(auto&&e:v){
        if(e.first==2){
            vec.push_back({4,e.second/2});
            vec.push_back({2,e.second%2});
            sum+=3*(e.second%2);
            sum+=5*(e.second/2);
        }else{
            sum+=(e.first+1)*e.second;
            vec.push_back(e);
        }
    }
    if(sum>200000){
        cout<<-1<<endl;
        return 0;
    }
    cout<<sum<<endl;
    
    vector<char> ans(sum);
    
    int cnt=-1;
    for(auto&&e:vec){
        for(int i=0;i<e.second;i++){
            if(cnt!=-1){
                cout<<cnt+1<<" "<<cnt+2<<endl;
            }
            cnt++;
            ans[cnt]='b';
        }
    }
    int las=-1;
    for(auto&&e:vec){
        for(int i=0;i<e.second;i++){
            las++;
            for(int j=0;j<e.first;j++){
                cnt++;
                cout<<las+1<<" "<<cnt+1<<endl;
                ans[cnt]='g';
            }
        }
    }
    for(auto&&e:ans)cout<<e<<" ";
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0