SOJ#46. 玩游戏game 题解

description：

一开始有两个数A和B，进行K轮游戏，每一轮可能有两种情况：

• 若 $A\le B$A≤B，本***作后 $B^{\prime }=B-A,A^{\prime }=A+A$B′=B−A,A′=A+A.
• 若 B<A， 本***作后 $A^{\prime }=A-B,B^{\prime }=B+B.$A′=A−B,B′=B+B.

请输出 $K$K轮游戏后 $\min (A,B)$min(A,B)的值。

solution：

• $k\le 10^7$k≤107
  直接 $O\left(k\right)$O(k)暴力即可

• $A,B\le 10^{3}andA,B\le 10^6$A,B≤103andA,B≤106

A+B是一个循环节的长度，这样就可以通过直接除掉循环节来减少运算次数，但是A，B大了之后循环节就枚举不出来了。

• A,B<=108

传统的找循环节⽅方法空间是 $O(A+B)$O(A+B)会超过内存限制

可以⽤用bitset把内存变成 $O\left(\right(A+B\left)/32\right)$O((A+B)/32)

bitset<200000000>F;

• A,B<=109

设 $S=A+B$S=A+B

若 A<=B(即S-A)，则A’ = 2A = 2A mod S

若 $A>B$A>B，则A’ = A - (S - A) = 2A - S = 2A mod S

所以答案为 $A\ast 2^{K}modS$A∗2KmodS

code:

刚开始的逐步骗分代码（ $65pts$65pts）:

//请输出k次后min（A,B)的值 
#include<cstdio>
using namespace std;
int min(int a,int b)
{
	if(a<=b)
	{
		return a;
	}
	else
	{
		return b;
	}
}
int x[10000005],y[10000005];
long long a,b,k;
void ANS()
{
	int flag=0;
	x[0]=a;
	y[0]=b;
	long long tmp=0,num=0;
	for(long long i=1;i<=k;i++)
	{
		if(x[i-1]<=y[i-1])
		{
			y[i]=y[i-1]-x[i-1];
			x[i]=x[i-1]*2;
		}
		else
		{
			x[i]=x[i-1]-y[i-1];
			y[i]=y[i-1]*2;
		}
		if(i==1)tmp=x[i];
		if(i!=1&&x[i]==tmp)
		{
			num=i;
			flag=1;
			break;
		}
	}
	if(flag==0)
	{
		printf("%d\n",min(x[k],y[k]));
		return;
	}
	num--;
	long long ans=k%num;
	printf("%d\n",min(x[ans],y[ans]));
}
int main()
{
	//freopen("game.in","r",stdin);
	//freopen("game.out","w",stdout); 
	scanf("%lld%lld%lld",&a,&b,&k);
	if(k<=10000000)//20%
	{
		for(long long i=1;i<=k;i++)
		{
			if(a<=b)
			{
				b=b-a;
				a=a+a;
			}
			else
			{
				a=a-b;
				b=b+b;
			}
		}
		printf("%d\n",min(a,b));
		return 0;
	}
	if(a<=1000&&b<=1000)//20%
	{
		ANS();
		return 0;
	}
	if(a<=1000000&&b<=1000000)//20%
	{
		ANS();
		return 0;
	}
	if(a<=100000000&&b<=100000000)//20% 
	{
		ANS();
		return 0;
	}
	else//听天由命 
	{
		ANS();
		return 0;
	}
} 
//955 812 828145516

/* 955253431 806956091 10000000 a=135061684 */

正解代码：

#include<cstdio>
using namespace std;
long long sqr(long long x)
{
	return x*x;
}
long long ksm(long long x,long long y,long long p)
{
	if(y==0)return 1;
	if(y%2==1)
	{
		return x*ksm(x,y-1,p)%p;
	}
	else
	{
		return sqr(ksm(x,y/2,p))%p;
	}
}
long long min(long long x,long long y)
{
	if(x<y)return x;
	else return y;
}
int main()
{
	//printf("%d\n",ksm(2,5,10));
	long long a,b,k;
	scanf("%lld%lld%lld",&a,&b,&k);
	long long ans=a*ksm(2,k,a+b)%(a+b);
	printf("%lld\n",min(ans,a+b-ans));
	return 0;
}