2015年12月16日 星期三

Codechef November Challenge 2015 Chef and cakes

/*
    能拿到蛋糕的機器人的編號x
    必定滿足 x=M+1 (MOD gcd(N,M))
    而很顯然的這樣的 x 有 N/gcd(N,M)個   
*/
// https://www.codechef.com/NOV15/problems/EGRCAKE/
#include <iostream>
#include <cstdio>
 
using namespace std;
 
int gcd(int x, int y)
{
    while( x && y )
    {
        if( x < y ) swap(x, y);
        x %= y;
    }
 
    return x+y;
}
 
int main()
{
    int T;
    scanf("%d", &T);
 
    while( T-- )
    {
        int N, M;
        scanf("%d %d", &N, &M);
 
        int GCD = gcd(N, M);
 
        if( GCD == 1 ) puts("Yes");
        else printf("No %d\n", N/GCD);
    }
}

沒有留言:

張貼留言