hdoj1222

不难得到有安全hole的条件是:
(1)n>=m:n能被m整除且m!=1
(2)m>n:
1)m%n!=0:n能被(m%n)整除且(m%n)!=1
2)m%n==0(因为这个没考虑导致run time error一次。。)
(3)注意特殊情况n=1,此时不管m是多少一定没有安全hole。。(因为这个WA一次。。)
起初在想一个比较傻的问题:n>m时是否可能出现第二(也可以是三、四等等)圈时没有走到访问过的点(错开了),而之后走第k圈的时候走到了一个以前访问过的点,之后循环访问这些点?
其实这是不可能的,这个问题有点二。。用反证可以证明:假设之后第k圈的时候访问了以前已经访问的某点,那么从这个时刻往前反推,当反推到第二圈时,可以发现推出的点并不是原来第二圈时走过的点(错开的点),矛盾。可知第二圈时不可能错开。(k=3试试,这样更好理解)

#include<stdio.h>
#include<stdlib.h>
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int m,n;
		scanf("%d %d",&m,&n);
		if(n==1)
			printf("NO\n");
		else if(n>=m)
		{
			if(n%m==0 && m!=1)
				printf("YES\n");
			else
				printf("NO\n");
		}
		else
		{
			if(m%n==0)
				printf("YES\n");
			else if((n%(m%n))==0 && m%n!=1)
				printf("YES\n");
			else
				printf("NO\n");
		}
	}
/system("pause");
return 0;
}

发表评论

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

*

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>