/**********************************************************************************************************************************
一座山上周围有n个洞，顺时针编号为0，1，2，……，n-1。
而一只狼从0号洞开始，顺时针方向计数，每遇到m个洞就进洞找兔子，
例如n=5 m=3 狼经过的洞依次为0，3，1，4，2，0
输入n、m。试问兔子有没有幸免的机会？

编写一个完整的程序  n m 由scanf输入

有幸免的机会输出Y
没有输出N

***********************************************************************************************************************************/
#include<iostream>
using namespace std;
/*
因为题目没给出n的范围，所以我只设了长度为1001
只能测n<=1000的情况 具体情况请题主自由设定tag长度
*/
int deal(int m,int n,int tag[])
{
    int drift(m);
    int count(1);
    while(drift!=0)
    {
        if(drift>=n)
            drift=drift%n;
        if(0==tag[drift])
        {
            count++;
            tag[drift]=1;
        }
        drift+=m;
        if(drift>=n)
            drift=drift%n;
    }
    if(count==n)
        return 0;
    else return 1;
}

void main()
{
    int m,n;
    cout<<"请输入m"<<endl;
    cin>>m;
    cout<<"请输入n"<<endl;
    cin>>n;
    int tag[1001];
    memset(tag,0,sizeof(tag));
    if(deal(m,n,tag))
        cout<<"Y"<<endl;
    else cout<<"N"<<endl;
}

/*上面这个算法是朋友的    觉得挺有趣   借了过来*/

评论