可以想象成有一个人从起点0处绕着一个圈长为mod个单位“跳步”，每跳一次必须跳step个单位（也就是可不能出现在i*step<pos<(i+1)*step的位置），而至少跳mod次恰好回到起点的话，就是Good Choice,如果在第mod次前就恰好到达起点则为Bad Choice

而我们知道，回到起点把所需的最短时间即是step和mod的最小公倍数，而若为Good Choice,显然最短时间又等于step*mod,由数论的知识gcd(step,mod)=step*mod/(step和mod的最小公倍数)=1

这样为Good Chance的充要条件就是gcd(step,mod)=1

输出
if(gcd(a,b)>1)
{
     printf("%10d%10d    Bad Choice\n\n",a,b);
}
else
{
     printf("%10d%10d    Good Choice\n\n",a,b);
}

• Re:解题思路 (4) allcomezy 2016-05-20 20:54:31