HDOJ 1222 Wolf and Rabbit

很好的一题,论坛一个朋友求助的,我就顺便试下了,奈何中午没睡,困死了。

下午醒了,可是…还是不会=。=

无奈去HDOJ的BBS求助,看到有几个人只说了句“互质”…

汗,自己举例子好好想想把…终于想通了,也懂了,只能说,此题经典!

这里把自己的思路贴出来:

*********************************************************************************

思路:
首先,大家可以把m=2,n=5和m=2,n=6的例子自己比划一下。
其次,考虑,一次走m格,共有n个洞,假设要想使安全洞为0,
怎么办?
这里要想使安全洞为0,则要走共有m*n格。
如果没走到m*n格,则必然有一些懂没走到。
再考虑,什么情况会使安全洞的值不为0,就如m=2,n=6
走过的洞的编号为0,2,4,0,起始是0,第四次又走到0了,
所以从4开始就和初始是一样的情况,之前没走到洞后面也永远不会走到。
这就是有安全洞的原因。
再说明白一点,就是在第x次(x<n),会又走到第0个洞,这样,即
(m*x)%n=0,
考虑如何会出现这种情况?
当m,n互质的时候,在第n次之前,一定不会走到第0个洞的。
而当m,n不互质时,假设m,n公约数为y,则在第第n/y次,会走到第0个洞
m*(n/y)%n=0;
而走到第0个洞后,自然也就和前面的路线一致了,没走到的始终就是没走到。

写得累死了,大家给我鼓掌鼓励下吧。。。=。=

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
 // Author: Tanky Woo
// HDOJ 1222
// Accepted 1222 0MS 208K 421B C++ Tanky Woo 
 
#include <iostream>
using namespace std;
 
int gcd(int x, int y)
{
	if(x < y)
	{
		x ^= y;
		y ^= x;
		x ^= y;
	}
	if(y == 0)
		return x;
	else
		return gcd(y, x%y);
}
int main()
{
	int nCases;
	int m, n;
	scanf("%d", &nCases);
	while(nCases--)
	{
		scanf("%d %d", &m, &n);
		if(gcd(m, n) == 1)
			printf("NO\n");
		else
			printf("YES\n");
	}
	return 0;
}

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

《HDOJ 1222 Wolf and Rabbit》有2个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注