链接：https://ac.nowcoder.com/acm/contest/3782/B
来源：牛客网
 

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

题目描述

给定两个正整数n，m。问能否构造出一个长度为n的字符串s[0..n-1]，满足以下两个条件：

1. 对于n的任意正因数d（d<n），d不是s的周期。

2. 对于∀i∈[0,m-1]，s[i mod n]=s[(i+m) mod n]。

输入描述:

输入包含多组数据。

第一行包括一个正整数T。

接下来T行，每行包括两个正整数n，m。

输出描述:

对于每组数据输出一行。若能构造出符合条件的字符串，输出“Yes”，否则输出“No”。（均不含引号）

示例1

输入

复制

7
1 3
3 5
3 6
7 2
6 3
10 6
10 8

输出

复制

Yes
No
Yes
Yes
No
Yes
No

说明

 

第一组：s="a"满足题意

第二组：需要满足s[0]=s[(0+5) mod 3]即s[0]=s[2]、s[1]=s[(1+5) mod 3]即s[1]=s[0]。故s[0]=s[1]=s[2]，1是s的周期，不合题意。

第三组：s="abc"满足题意

第四组：s="ababccc"满足题意

第五组：需要满足s[0]=s[3],s[1]=s[4],s[2]=s[5]。故3是s的周期，不合题意。

第六组：s="abcdababcd"满足题意

第七组：需要满足s[0]=s[8],s[1]=s[9],s[2]=s[0],s[3]=s[1],s[4]=s[2],s[5]=s[3],s[6]=s[4],s[7]=s[5]，即s[0]=s[2]=s[4]=s[6]=s[8],s[1]=s[3]=s[5]=s[7]=s[9]。故2是s的周期，不合题意。

备注:

 

T=1*106

1≤n,m≤1018

可以认为字符集的大小大于n。

字符串周期的定义：

对于字符串s[0..l-1]，若正整数t满足对于∀i∈[0,l-t-1]，s[i]=s[i+t]，则称t为字符串s的周期。

本题输入规模较大，请使用较快的读入方式或者使用以下读入模板：

inline long long read() {

    long long tmp=0, fh=1; char c=getchar();

    while (c<'0'||c>'9') {if (c=='-') fh=-1; c=getchar();}

    while (c>='0'&&c<='9') tmp=tmp*10+c-48, c=getchar();

    return tmp*fh;

}

用法:

long long n=read(), m=read();

 

n > m时，发现如果n - m <= gcd(n, m) 不合题意。n < m时，发现只有m % n == 0时才符合题意。

综合以上：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

typedef long long ll;
const int N = 1e5 + 5;

inline long long read()
{
    long long tmp=0, fh=1;
    char c=getchar();
    while (c<'0'||c>'9')
    {
        if (c=='-')
            fh=-1;
        c=getchar();
    }
    while (c>='0'&&c<='9')
        tmp=tmp*10+c-48, c=getchar();
    return tmp*fh;
}

ll gcd(ll a, ll b)
{
    return b?gcd(b, a%b):a;
}

int main()
{
    ll n, m, t;
    t = read();
    while(t--)
    {
        n = read();
        m = read();
        if((m % n == 0) || gcd(n, m) < (n - m))    ///m % n == 0要加上括号，亲测会WA
        {
            cout<<"Yes"<<'\n';
        }
        else
        {
            cout<<"No"<<'\n';
        }
    }
    return 0;
}