Blog·Tanky WooABOUTRSS

HDOJ 1222 Wolf and Rabbit

24 Jul 2010
这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。

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

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

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

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

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


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

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

 

 // Author: Tanky Woo
// HDOJ 1222
// Accepted 1222 0MS 208K 421B C++ Tanky Woo 

#include 
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;
}