Submission #15235

#	Time	Username	Problem	Language	Result	Execution time	Memory
15235		tonyjjw	로봇 심판의 님 게임 (kriii3_F)	C++98	79 / 79	622 ms	2644 KiB

S

#include<stdio.h>
int n,m,k;
int p[20];
long long int nim[25];
long long int ns[25];
long long int pp[100000];
long long int qq[100000];
long long int gcd(long long int x,long long int y){
	if(x==0)return y;
	return gcd(y%x,x);
}
long long int f(long long int x){
	long long int i,res=0;
	for(i=0;i<(1<<(n+m));i++){
		res+=(x/pp[i])*qq[i];
	}
	return res;
}
int main(){
	int i,j;
	long long int ii,jj,kk;
	scanf("%d%d%d",&n,&m,&k);
	for(i=0;i<n;i++){
		scanf("%d",&p[i]);
	}
	for(i=0;i<m;i++){
		scanf("%d",&p[i+n]);
	}
	for(i=0;i<k;i++){
		scanf("%lld",&nim[i]);
		for(j=0;j<n;j++){
			if(nim[i]%p[j]==0)break;
		}
		if(j!=n)nim[i]=0;
		for(j=0;j<m;j++){
			if(nim[i]%p[n+j]==0)break;
		}
		if(j==m)nim[i]=0;
	}
	for(i=0;i<(1<<(n+m));i++){
		ii=1;
		jj=0;
		kk=0;
		for(j=0;j<n+m;j++){
			if(i&(1<<j)){
				if(j<n)jj++;
				else kk++;
				ii/=gcd(ii,p[j]);
				ii*=p[j];
			}
			if(ii>(1e12)+(1e8)){
				ii=(1e12)+(1e8);
			}
		}
		pp[i]=ii;
		for(j=0;j<k;j++){
			if(jj%2==0&&kk%2==1){
				ns[j]+=nim[j]/ii;
				qq[i]=1;
			}
			else if(jj%2==0&&kk!=0){
				ns[j]-=nim[j]/ii;
				qq[i]=-1;
			}
			if(jj%2==1&&kk%2==1){
				ns[j]-=nim[j]/ii;
				qq[i]=-1;
			}
			else if(jj%2==1&&kk!=0){
				ns[j]+=nim[j]/ii;
				qq[i]=1;
			}
		}
	}
	kk=0;
	for(i=0;i<k;i++){
		kk^=ns[i];
	}
	for(i=0;i<k;i++){
		if(ns[i]!=0&&ns[i]==kk){
			ii=-1;
			for(j=42;j>=0;j--){
				ii+=1LL<<j;
				if(ii>nim[i])ii-=1LL<<j;
				else if(ii-f(ii)==nim[i]-ns[i])ii-=1LL<<j;
			}
			ii++;
			printf("%lld %lld\n",nim[i]-ns[i]+1,nim[i]-ii);
		}
		else if(ns[i]>(ns[i]^kk)){
			ii=-1;
			for(j=42;j>=0;j--){
				ii+=1LL<<j;
				if(f(ii)>=(ns[i]^kk))ii-=1LL<<j;
			}
			ii++;
			printf("1 %lld\n",nim[i]-ii);
		}
		else{
			printf("0 0\n");
		}
	}
	
	return 0;
}

• Subtask 1: 28 / 28
• Subtask 2: 51 / 51