結果

問題 No.443 GCD of Permutation
ユーザー smiken_61smiken_61
提出日時 2016-11-13 20:58:15
言語 C++11
(gcc 13.3.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 6,622 bytes
コンパイル時間 1,954 ms
コンパイル使用メモリ 163,420 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-13 23:57:56
合計ジャッジ時間 2,414 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 AC 1 ms
5,248 KB
testcase_02 AC 1 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 2 ms
5,248 KB
testcase_05 AC 2 ms
5,248 KB
testcase_06 AC 1 ms
5,248 KB
testcase_07 AC 1 ms
5,248 KB
testcase_08 AC 1 ms
5,248 KB
testcase_09 AC 2 ms
5,248 KB
testcase_10 AC 2 ms
5,248 KB
testcase_11 AC 2 ms
5,248 KB
testcase_12 AC 2 ms
5,248 KB
testcase_13 AC 1 ms
5,248 KB
testcase_14 AC 2 ms
5,248 KB
testcase_15 AC 2 ms
5,248 KB
testcase_16 AC 2 ms
5,248 KB
testcase_17 AC 2 ms
5,248 KB
testcase_18 AC 2 ms
5,248 KB
testcase_19 AC 1 ms
5,248 KB
testcase_20 AC 2 ms
5,248 KB
testcase_21 AC 1 ms
5,248 KB
testcase_22 AC 2 ms
5,248 KB
testcase_23 AC 2 ms
5,248 KB
testcase_24 AC 1 ms
5,248 KB
testcase_25 AC 1 ms
5,248 KB
testcase_26 AC 2 ms
5,248 KB
testcase_27 AC 2 ms
5,248 KB
testcase_28 AC 2 ms
5,248 KB
testcase_29 AC 2 ms
5,248 KB
testcase_30 AC 2 ms
5,248 KB
testcase_31 AC 2 ms
5,248 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

            #include <bits/stdc++.h>
            #include<iostream>
            #include<cstdio>
            #include<vector>
            #include<queue>
            #include<map>
            #include<cstring>
            #include<string>
            #include <math.h>
            #include<algorithm>
        //    #include <boost/multiprecision/cpp_int.hpp>
            #include<functional>
          #define int long long
            #define inf  1000000007
            #define pa pair<int,int>
    #define ll long long
            #define pal pair<ll,ll>
            #define ppa pair<int,pa>
            #define  mp make_pair
            #define EPS (1e-10)
            #define equals(a,b) (fabs((a)-(b))<EPS)
     
            using namespace std;
     
            class Point{
            	public:
            	double x,y;
            	Point(double x=0,double y=0):x(x),y(y) {}
            	Point operator + (Point p) {return Point(x+p.x,y+p.y);}
            	Point operator - (Point p) {return Point(x-p.x,y-p.y);}
            	Point operator * (double a) {return Point(x*a,y*a);}
            	Point operator / (double a) {return Point(x/a,y/a);}
            	double absv() {return sqrt(norm());}
            	double norm() {return x*x+y*y;}
            	bool operator < (const Point &p) const{
            		return x != p.x ? x<p.x: y<p.y;
            	}
            	bool operator == (const Point &p) const{
            		return fabs(x-p.x)<EPS && fabs(y-p.y)<EPS;
            	}
            };
            typedef Point Vector;
     
            struct Segment{
            Point p1,p2;
            };
     
        double hen(Vector a){
        if(fabs(a.x)<EPS && a.y>0) return acos(0);
        else if(fabs(a.x)<EPS && a.y<0) return 3*acos(0);
        else if(fabs(a.y)<EPS && a.x<0) return 2*acos(0);
        else if(fabs(a.y)<EPS && a.x>0) return 0.0;
        else if(a.y>0) return acos(a.x/a.absv());
        else return 2*acos(0)+acos(-a.x/a.absv());
     
        }
     
            double dot(Vector a,Vector b){
            	return a.x*b.x+a.y*b.y;
            }
            double cross(Vector a,Vector b){
            	return a.x*b.y-a.y*b.x;
            }
        
            //----------------kokomade temple------------
int x,y,n,m;
string s;
int keta[10]={0};


int gcd(int v,int b){
	if(v>b) return gcd(b,v);
	if(v==b) return b;
	if(b%v==0) return v;
	return gcd(v,b%v);
}

    signed main(){
int souwa=0;
    	cin>>s;
    	int l=s.length();
    	for(int i=0;i<l;i++){
    		keta[s[i]-'0']++;
    		souwa += (s[i]-'0');
    	}
    	int syurui=0;
    	for(int i=0;i<10;i++){
    		if(keta[i]) syurui++;
    		
    	}
    	if(syurui==1){
    		cout<<s<<endl;
    		return 0;
    	}
    	int g=45360;
    	for(int i=0;i<10;i++){
    		for(int j=i+1;j<10;j++){
    			if(!(keta[i]>0 && keta[j]>0)) continue;
    			g=gcd(g,9*(j-i));
    		}
    		
    	}
    	
    	if(g==9){
    		if(souwa%9==0) cout<<9<<endl;
    		else if(souwa % 3==0) cout<<3<<endl;
    		else cout<<"1"<<endl;
    		return 0;
    	}
    	if(g==18){
    		if((s[0]-'0')%2==0){
    			if(souwa%9==0) cout<<"18"<<endl;
    		else if(souwa % 3==0) cout<<"6"<<endl;
    		else cout<<"2"<<endl;
    		}
    		else{
    			if(souwa%9==0) cout<<"9"<<endl;
    		else if(souwa % 3==0) cout<<"3"<<endl;
    		else cout<<"1"<<endl;
    		}
    		
    		
    		return 0;
    	}
    		if(g==27){
    			int y=0;
    			for(int i=0;i<l;i++){
    				y*=10;
    				y += (s[i]-'0');
    				y%=27;
    			}
    			if(y==0) cout<<"27"<<endl;
    			else if(souwa%9==0) cout<<"9"<<endl;
    		else if(souwa % 3==0) cout<<"3"<<endl;
    		else cout<<"1"<<endl;
    		
    		
    		
    		return 0;
    	}
    		if(g==36){
    		
    			if(((s[0]-'0')*10+(s[1]-'0'))%4==0){
    				if(souwa%9==0) cout<<"36"<<endl;
    		else if(souwa % 3==0) cout<<"12"<<endl;
    		else cout<<"4"<<endl;
    				
    			}
    			
    		else if((s[0]-'0')%2==0){
    			if(souwa%9==0) cout<<"18"<<endl;
    		else if(souwa % 3==0) cout<<"6"<<endl;
    		else cout<<"2"<<endl;
    		}
    		else{
    			if(souwa%9==0) cout<<"9"<<endl;
    		else if(souwa % 3==0) cout<<"3"<<endl;
    		else cout<<"1"<<endl;
    		}
    		
    		return 0;
    	}
    		if(g==45){
    		
    			if((s[0]-'0')%5==0){
    			if(souwa%9==0) cout<<"45"<<endl;
    		else if(souwa % 3==0) cout<<"15"<<endl;
    		else cout<<"5"<<endl;
    		}
    		else{
    			if(souwa%9==0) cout<<"9"<<endl;
    		else if(souwa % 3==0) cout<<"3"<<endl;
    		else cout<<"1"<<endl;
    		}
    		
    		
    		return 0;
    	}
    		if(g==54){
    		int y=0;
    			for(int i=0;i<l;i++){
    				y*=10;
    				y += (s[i]-'0');
    				y%=27;
    			}
    			
    			if((s[1]-'0')%2==0){
    				if(y==0) cout<<"54"<<endl;
    			else if(souwa%9==0) cout<<"18"<<endl;
    		else if(souwa % 3==0) cout<<"6"<<endl;
    		else cout<<"2"<<endl;
    			}
    			else{
    				if(y==0) cout<<"27"<<endl;
    			else if(souwa%9==0) cout<<"9"<<endl;
    		else if(souwa % 3==0) cout<<"3"<<endl;
    		else cout<<"1"<<endl;
    			}
    		
    		
    		return 0;
    	}
    		if(g==63){
    		int y=0;
    			for(int i=0;i<l;i++){
    				y*=10;
    				y += (s[i]-'0');
    				y%=7;
    			}
    			if(y==0){
    				if(souwa%9==0) cout<<"63"<<endl;
    		else if(souwa % 3==0) cout<<"21"<<endl;
    		else cout<<"7"<<endl;
    			}
    			else{
    				if(souwa%9==0) cout<<"9"<<endl;
    		else if(souwa % 3==0) cout<<"3"<<endl;
    		else cout<<"1"<<endl;
    			}
    		
    		return 0;
    	}
    		if(g==72){
    			int r=0;
    			for(int i=0;i<min(3ll,l);i++){
    				r*=10;
    				r += (s[i]-'0');
    			}
    			if(r%8==0){
    				if(souwa%9==0) cout<<"72"<<endl;
    		else if(souwa % 3==0) cout<<"24"<<endl;
    		else cout<<"8"<<endl;
    			}
    			else if(((s[0]-'0')*10+(s[1]-'0'))%4==0){
    				if(souwa%9==0) cout<<"36"<<endl;
    		else if(souwa % 3==0) cout<<"12"<<endl;
    		else cout<<"4"<<endl;
    				
    			}
    			
    		else if((s[0]-'0')%2==0){
    			if(souwa%9==0) cout<<"18"<<endl;
    		else if(souwa % 3==0) cout<<"6"<<endl;
    		else cout<<"2"<<endl;
    		}
    		else{
    			if(souwa%9==0) cout<<"9"<<endl;
    		else if(souwa % 3==0) cout<<"3"<<endl;
    		else cout<<"1"<<endl;
    		}
    		
    		
    		return 0;
    	}
    	if(g==81){
    		if(keta[9]%9==0){
    			cout<<"81"<<endl;
    		}
    		else if(keta[9]%3==0){
    			cout<<"81"<<endl;
    		}
    		else if(souwa%9==0) cout<<"9"<<endl;
    		else if(souwa % 3==0) cout<<"3"<<endl;
    		else cout<<"1"<<endl;
    		
    		return 0;
    	}
    //	printf("%.10f\n",ans);
    	return 0;
    }
0