首页 > 代码库 > NYOJ 854 留恋

NYOJ 854 留恋

留恋

时间限制:1000 ms  |  内存限制:65535 KB
难度:2
描述

大家都知道,高中的时候,座位基本都是固定的,但是对于视力不好却又坐在后面的人是很不公平的。

念情的高中班主任安哥是个非常好的班主任,他为每个人着想,制定了一种的换位规则,每周执行一次:

        每次都向右下角移动一个位置(即本周坐(0,1),则下周坐(1,2))

        若已移动到边上,则返回顶部(即在行数为3的情况下,本周在(2,n),则下周在(0,n+1),列同)

现在念情想知道,如果教室有(n*m)个座位,他能不能把所有的座位都坐一次呢?(假设念情读高中的时间无限

输入
第一行一个整数N表示N组测试数据
接下来N行每行两个整数n,m表示教室的座位
1<n<10000
1<m<10000
输出
若念情能够把座位都坐一边,则输出Possible,否则输出Impossible
样例输入
3
2 3
2 2
3 6
样例输出
Possible
Impossible
Impossible
思路:这道其实是道数学题,我一开用深搜写的,诶……真坑啊   其实如果两个数的最大公约数为1就有解,否则就无解
AC代码:
#include<stdio.h>
int gcd(int a,int b)
{
    
	int r;
	r=a%b;
	if(r==0) return b;
	else return gcd(b,r);
}
int main()
{
	int N,n,m;
	scanf("%d",&N);
	while(N--)
	{
     scanf("%d%d",&n,&m);
	 if(gcd(n,m)==1)
		 printf("Possible\n");
	 else printf("Impossible\n");
	}

  //printf("%d\n",gcd(2,3));
  //system("pause");
  return 0;
}