Submission #15314

#	Time	Username	Problem	Language	Result	Execution time	Memory
15314		progressive	로봇 심판의 님 게임 (kriii3_F)	C++14	79 / 79	388 ms	2108 KiB

S

#include<cstdio>
#include<algorithm>
using namespace std;
inline long long lcm(long long A,long long B)
{
	return A*B/__gcd(A,B);
}
//!( n(p1|x v p2|x) - n(p1|x v p2|x v q1|x v q2|x))
int N,M,K;
int P[20],Q[20];
long long LCM[131072];
long long A[50];
long long cnt[50];
void calclcm()
{
	for(int q=0;q<(1<<M);q++)
	{
		for(int i=0;i<(1<<N);i++)
		{
			int idx=q*(1<<N)+i;
			LCM[idx]=1;
			bool overflow=false;
			for(int j=0;j<N;j++)
			{
				if(i&(1<<j)) LCM[idx]=lcm(LCM[idx],P[j]);
				if(LCM[idx]>1000000000000LL)
				{
					LCM[idx]=-1;
					overflow=true;
					break;
				}
			}
			if(overflow) continue;
			for(int j=0;j<M;j++)
			{
				if(q&(1<<j)) LCM[idx]=lcm(LCM[idx],Q[j]);
				if(LCM[idx]>1000000000000LL)
				{
					LCM[idx]=-1;
					overflow=true;
					break;
				}				
			}
		}
	}
}
long long count(long long A)
{
	long long cnt=0;
	for(int i=0;i<(1<<N);i++)
	{
		if(LCM[i]==-1LL) continue;
		int parity=0;
		for(int j=0;j<N;j++)
			if(i&(1<<j))
				parity++;
		if(parity%2==0) cnt+=A/LCM[i];
		else cnt-=A/LCM[i];
	}
	
	for(int i=0;i<(1<<N);i++)
	{
		for(int q=0;q<(1<<M);q++)
		{
			if(LCM[i+q*(1<<N)]==-1LL) continue;
			int parity=1;
			for(int j=0;j<N;j++)
				if(i&(1<<j))
					parity++;
			for(int j=0;j<M;j++)
				if(q&(1<<j))
					parity++;
			if(parity%2==0) cnt+=A/(LCM[i+q*(1<<N)]);
			else cnt-=A/(LCM[i+q*(1<<N)]);
		}
	}
	return cnt;
}
int main()
{
	scanf("%d%d%d",&N,&M,&K);
	for(int i=0;i<N;i++) scanf("%d",P+i);
	for(int i=0;i<M;i++) scanf("%d",Q+i);
	calclcm();
	for(int i=0;i<K;i++)
	{
		scanf("%lld",A+i);
		cnt[i]=count(A[i]);
		//printf("%lld: %lld\n",A[i],cnt[i]);
	}
	long long grundy=0;
	for(int i=0;i<K;i++)
	{
		bool discard=false;
		for(int j=0;j<N;j++)
			if(A[i]%P[j]==0) discard=true;
		int dcnt=0;
		for(int k=0;k<M;k++)
			if(A[i]%Q[k]==0) dcnt++;
		if(discard || dcnt==0) continue;
		grundy^=cnt[i];
	}
	//fprintf(stderr,"%lld",grundy);
	if(grundy==0LL)
	{
		for(int i=0;i<K;i++)
			puts("0 0");
		return 0;
	}
	for(int i=0;i<K;i++)
	{
		bool discard=false;
		for(int j=0;j<N;j++)
		{
			if(A[i]%P[j]==0)
				discard=true;
		}
		int dcnt=0;
		for(int k=0;k<M;k++)
		{
			if(A[i]%Q[k]==0) dcnt++;
		}
		long long grundytomake=grundy^cnt[i];
		if(discard || dcnt==0 || cnt[i]<=grundytomake)
		{
			puts("0 0");
			continue;
		}
		if(grundytomake==0LL)
		{
			long long x=A[i];
			while(true)
			{
				bool discard=false;
				for(int j=0;j<N;j++)
					if(x%P[j]==0) discard=true;
				int dcnt=0;
				for(int k=0;k<M;k++)
					if(x%Q[k]==0) dcnt++;
				if(discard || dcnt==0) break;
				x--;
			}
			printf("%lld %lld\n",A[i]-cnt[i]+1,A[i]-x);
			continue;
		}
		else
		{//find min grundytomake
			long long lo=0;// <grundytomake
			long long hi=A[i]; //>=grundytomake
			while(lo+1!=hi)
			{
				long long mi=(lo+hi)/2;
				if(count(mi)<grundytomake) lo=mi;
				else hi=mi;
			}
			printf("%lld %lld\n",1LL,A[i]-hi);
		}
	}
	return 0;
}

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