codeforces515B

Drazil and His Happy Friends

Drazil有很多朋友，他们中有些人是快乐的，有些人是不快乐的。 Drazil想让他的朋友变得快乐。于是，他发明了以下的计划。

在他的朋友中，有n个男孩和m个女孩。我们把男孩从0到n-1编号，女孩从0到m-1编号。在第i天，Drazil邀请第i mod n个男孩和第i mod m个女孩一起吃饭（注意i从0开始）。如果两个人之中有一个是快乐的，那么另外一个也会变得快乐，否则，这两个人的心情状态不会改变。一个人一旦成为快乐的人（或者他原本就是快乐的），他能保持永远快乐。

Drazil想知道他是否可以使用该计划，使得他所有的朋友都变得快乐。

Input

第一行包含两个整数n和m（1≤n，m≤100）。

第二行包含整数b（0≤b≤n），表示Drazil的男生朋友中目前是快乐男生的数量，然后有b个不同的整数X1，X2，...，Xb（0≤Xi<n），表示这些快乐男生的编号。

第三行包含整数g（0≤g≤m），表示Drazil的女生朋友中目前是快乐女生的数量，然后有g个不同的整数Y1，Y2，...，Yg（0≤Yj<m），表示这些快乐女生的编号。

题目保证输入数据中至少有一个人不快乐。

Output

如果 Drazil能使得所有的朋友都变得快乐，就输出Yes，否则输出No

Sample Input

输入样例1：

2 3

1 0

输入样例2：

2 4

1 0

1 2

输入样例3：

2 3

1 0

1 1

Sample Output

输出样例1：

Yes

输出样例2：

输出样例3：

Yes

sol：暴力枚举就可以，显然枚举到max(n,m)*n*m是可以的，但没必要这么大，只要到2*n*m就可以了（应该十分显然吧）

#include <bits/stdc++.h>
using namespace std;
typedef int ll;
inline ll read()
{
    ll s=0;
    bool f=0;
    char ch=' ';
    while(!isdigit(ch))
    {
        f|=(ch=='-'); ch=getchar();
    }
    while(isdigit(ch))
    {
        s=(s<<3)+(s<<1)+(ch^48); ch=getchar();
    }
    return (f)?(-s):(s);
}
#define R(x) x=read()
inline void write(ll x)
{
    if(x<0)
    {
        putchar('-'); x=-x;
    }
    if(x<10)
    {
        putchar(x+'0');    return;
    }
    write(x/10);
    putchar((x%10)+'0');
    return;
}
#define W(x) write(x),putchar(' ')
#define Wl(x) write(x),putchar('
')
const int N=105;
int n,m;
bool Boy[N],Girl[N];
int main()
{
    int i,cnt;
    R(n); R(m);
    R(cnt); for(i=1;i<=cnt;i++) Boy[read()]=1;
    R(cnt); for(i=1;i<=cnt;i++) Girl[read()]=1;
    for(i=1;i<=((n*m)<<1);i++) if(Boy[i%n]||Girl[i%m])
    {
        Boy[i%n]=Girl[i%m]=1;
    }
    for(i=0;i<n;i++) if(!Boy[i]) return 0*puts("NO");
    for(i=0;i<m;i++) if(!Girl[i]) return 0*puts("NO");
    puts("YES");
    return 0;
}

View Code