ACM基础题

Problem A：Euclid's Game（欧几里德游戏）

题目的大意为：在一块板上一开始写有两个不相等的正整数。两个玩家交替写数字，每一次，当前玩家都必须在板上写出任意两个板上数字的差，而且这个数字必须是新的，也就是说，不能与板上任何一个已有的数字相同。当玩家再也写不出新数字时，他就输了。假设有A、B两个玩家，A先写，B后写。对于给定的两个数字，写程序判断是 A赢还是B赢。

提示：A赢还是B赢的关键是找出能写在板上的数字的个数，如果是奇数个数字可写，则A赢，如果是偶数个，则B赢。能写在板上的数字个数刚好可以用欧几里德算法（GCD）得到，假设开始数板上的两个数字为M和N，且M>N，则能写在板上的数字个数=M/GCD(M,N)，因此，只需要判断该数字的奇数还是偶数即可。（算法略）

Problem B：Locker doors（带锁的门）

题目大意：在走廊上有n个带锁的门，从1到n依次编号。最初所有的门都是关着的。我们从门前经过n次，每一次都从1号门开始。在第i次经过时（i=1,2,..., n）我们改变i的整数倍号锁的状态：也就是如果门是关的，就打开它；如果门是打开的，就关上它。举例来说，第一次经过后，所有的门都是打开的；第二次经过后，偶数门是关着的，奇数门是开着的；以此类推，在最后一次经过后，有多少门是开着的。

提示：门的状态只有两种，没经过一次，状态就会发生变化。如果一道门经过奇数次，那么结果状态和原始状态就会不一样，而经过偶数次则不会发生变化。因此问题的关键就是找出那些经过奇数次的门有多少道。很幸运，那些门的编号正好是整数i的完全平方数即1，4，9，16，...，因此只需要找出这样的数字有多少个即可。（算法略）

#include <iostream>
using namespace std;

int main()
{
	int n,i,j,sum=0;
	cin>>n;
	int * a = new int[n+1];
	for(i=0; i<n+1; i++)
		a[i]=0;

	for (i=1; i<=n; i++)
	{
		for (j=1; j<=n; j++)
		{
			if (j%i==0)
			{
				if(a[j]==0) a[j]=1;
				else a[j]=0;
			}
		}
	}

	for (i=1; i<=n; i++)
	{
		if(a[i]==1) sum++;
	}

	cout<<sum<<endl;
	return 0;
}