題面：

D - Human or Pig Time Limit:2000MS????Memory Limit:65536KB????64bit IO Format:%lld & %llu SubmitStatusPracticeZOJ 3513

Description

A man is lost in a strange world. In this world, he is a human in the daytime, and he will become a pig at night. The strange world is rectangle which is seperated into many 1 * 1 grids, from (0,0) to (X,Y). Every grid has a coordinate (x , y ). If he is in the grid ( x , y ), he can jump to grid (x - k * y , y ) or ( x , y - k * x ). k is a positive integer. For example, if he is in the grid (4,9), he can only jump to the grid (4,1) or (4,5). At night, he jumps to another grid at 1:00 AM as pig. In the daytime, he jumps to another grid at 1:00 PM as a human. So he will jump exactly twice everyday.

As the figure show, the grids ( x , 0 ), ( 0 , y ) (0 <= x <= X, 0 <=y <= Y ) are the river. When he Jump into the river, he will change from pig to human or change from human to pig immediately. And his property will never change from then on. It means that if he jump into the river in the daytime, he will be a pig forever. He want to jump into the river at night, so that he change from pig to human immediately, and can be a human forever, never become a pig again.

When he become a pig at night, he will jump to a grid whose coordinate satisfies (x - k * y , y ) or ( x , y - k * x ) arbitrarily. He will not jump out of the strange world either in the daytime or at night. At the beginning, he is at the grid (x0 , y0 ). To ensure that he can jump into the river as a pig at last, at the beginning, he can choose to start as a pig at night or as a human in the daytime. You need to determine what time (day or night) to start in every grid of the strange world excecpt the river. Use a matrix to display it.

Input

There are multiple cases (no more than 100).

Each case contain two integers X and Y (1 <= X * Y <= 40000) indicating the size of the strange world.

Output

For each test case i, print case number in the form "Case #i" in one single line. And there is aX*Y matrix. The j th charater of the i th line indicating what time (day or night) to start in the grid (i , j ). 'H' means that to ensure that he can jump into the river as a human, he needs to start as a human in the daytime. 'P' means that to ensure that he can jump into the river as a human, he needs to start as a pig at night.

Sample Input

1?2
2?3

Sample Output

Case?#1:
PH
Case?#2:
PHH
HPP

題目大意：

??? 給定一個初始坐標，（x,y）可以移動到(x-k*y,y)或者(x,y-k*x)，k為正整數(shù)。初始給定的點在一張地圖上，地圖上的(x,0),(0,y)是一條神奇的河，跳進去就會發(fā)生身份的轉(zhuǎn)變，即豬變?nèi)?，人變豬，且不會再發(fā)生改變。很重要的一點是，狀態(tài)為豬是笨的，他的選擇是隨意的，而人的狀態(tài)是明智的，他是奔著最后可以變?yōu)槿说哪繕巳サ摹Ｆ鋵?，當x,y相對大小不變關(guān)系時，只能移動x，或者y。故比如x>y時，可以移動x/y次。那么就可以視這些可移動的為一個序列。進而可以轉(zhuǎn)換為取石子的模型，每次可移動的步數(shù)，可以視為一堆石子。與普通取石子模型不同的是，這道題需要按固定順序取。因為，要保證最后那一跳是豬變?nèi)?，所以如果某個位置是填豬，也就是無論他怎么跳，最后都會跳到豬變?nèi)说臓顟B(tài)，若某個位置填人，那么就是該位置，不能任由豬亂跳，需要人掌控。那么，人是如何做到掌控的呢，像一堆石子只有1個，人和豬是沒有選擇余地的，只能乖乖跳。但只要數(shù)量大于1，那么人就可以選擇，比如，是留一個給豬跳，還是全都自己跳。因此，只要數(shù)取石子序列從最開始開始的連續(xù)1的個數(shù)，然后確保第一個出現(xiàn)大于1的位置是留給人的就ok啦。

代碼：

#include#include#include#include#includeusing?namespace?std;
int?cal(int?x,int?y)
{
	int?tc=0,tx=0;
	if(x<y)
	{
		x^=y;
		y^=x;
		x^=y;
	}
	while(1)
	{
		tx=x/y;
		if(tx==1)
		??tc++;
		else
		??break;
		x%=y;
		if(x==0)break;
		x^=y;
		y^=x;
		x^=y;
	}
	return?tc;
}
int?main()
{
??int?n,m,cnt=1,res;
??while(~scanf("%d%d",&n,&m))
??{
?????printf("Case?#%d:n",cnt++);
?????for(int?i=1;i<=n;i++)
?????{
		?for(int?j=1;j<=m;j++)
		?{
			?res=cal(i,j);
			?if(res%2)
			????printf("P");
			?else
			????printf("H");
	?????}
	?????printf("n");
	?}
??}
??return?0;
}