#1008099 (C++23) No.2929 Miracle Branch

提出ソース

結果

問題	No.2929 Miracle Branch
ユーザー	nouka28
提出日時	2024-09-07 11:25:05
言語	C++23 (gcc 12.3.0 + boost 1.83.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

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,812 KB
testcase_01	AC	2 ms 6,816 KB
testcase_02	AC	2 ms 6,944 KB
testcase_03	AC	2 ms 6,944 KB
testcase_04	AC	2 ms 6,940 KB
testcase_05	AC	2 ms 6,944 KB
testcase_06	AC	3 ms 6,940 KB
testcase_07	AC	2 ms 6,944 KB
testcase_08	AC	2 ms 6,944 KB
testcase_09	AC	2 ms 6,944 KB
testcase_10	AC	3 ms 6,944 KB
testcase_11	AC	2 ms 6,944 KB
testcase_12	AC	2 ms 6,940 KB
testcase_13	AC	2 ms 6,940 KB
testcase_14	AC	3 ms 6,944 KB
testcase_15	AC	3 ms 6,940 KB
testcase_16	AC	2 ms 6,940 KB
testcase_17	AC	2 ms 6,940 KB
testcase_18	AC	4 ms 6,940 KB
testcase_19	AC	5 ms 6,940 KB
testcase_20	AC	8 ms 6,944 KB
testcase_21	AC	15 ms 6,944 KB
testcase_22	AC	2 ms 6,940 KB
testcase_23	AC	26 ms 6,944 KB
testcase_24	AC	90 ms 6,944 KB
testcase_25	AC	11 ms 6,940 KB
testcase_26	AC	3 ms 6,944 KB
testcase_27	AC	3 ms 6,940 KB
testcase_28	AC	2 ms 6,940 KB
testcase_29	AC	2 ms 6,944 KB
testcase_30	AC	2 ms 6,940 KB
testcase_31	AC	2 ms 6,940 KB
testcase_32	AC	2 ms 6,940 KB
testcase_33	AC	2 ms 6,940 KB
testcase_34	AC	289 ms 6,940 KB
testcase_35	AC	289 ms 6,944 KB
testcase_36	AC	2 ms 6,940 KB
testcase_37	AC	292 ms 6,944 KB
testcase_38	AC	286 ms 6,940 KB
testcase_39	AC	301 ms 6,940 KB
testcase_40	AC	294 ms 6,940 KB
testcase_41	AC	298 ms 6,944 KB
testcase_42	AC	291 ms 6,940 KB
testcase_43	AC	296 ms 6,944 KB
testcase_44	AC	289 ms 6,944 KB
testcase_45	AC	2 ms 6,940 KB

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

ソースコード

raw source code

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

yukicoder

結果

テストケース

ソースコード