题意
Translated by paryerhgq
Drazil有很多朋友，他们中有些人是快乐的，有些人是不快乐的。 Drazil想让他的朋友变得快乐。于是，他发明了以下的计划。
在他的朋友中，有n个男孩和m个女孩。我们把男孩从0到n-1编号，女孩从0到m-1编号。在第i天，Drazil邀请第i mod n个男孩和第i mod m个女孩一起吃饭（注意i从0开始）。如果两个人之中有一个是快乐的，那么另外一个也会变得快乐，否则，这两个人的心情状态不会改变。一个人一旦成为快乐的人（或者他原本就是快乐的），他能保持永远快乐。
Drazil想知道他是否可以使用该计划，使得他所有的朋友都变得快乐。
思路
注意到问题规模比较小，所以我们直接模拟就好了但是我们要至少操作2*nm次才可以。
有一种不暴力的解法，我们发现我们最后能够变快乐的人的编号x一定满足x = a (mod gcd(boy,girl))，其中boy是男生人数，girl是女生人数，a是某个一开始就快乐的人的编号，这样我们只要扫一遍所有快乐的人，在模gcd(boy,girl)的完全剩余系里标记一下就搞定了。
代码
暴力：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
#include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <stack> #include <cmath> #include <map> using namespace std; bool dansei[101]; bool jousei[101]; int main(){ memset(dansei, 0, sizeof(dansei)); memset(jousei, 0, sizeof(jousei)); int n = 0,m = 0; scanf(" %d %d",&n,&m); int nx = 0,mx = 0; scanf(" %d",&nx); for (int i = 1; i <= nx; i++) { int pos = 0; scanf(" %d",&pos); dansei[pos] = true; } scanf(" %d",&mx); for (int i = 1; i <= mx; i++) { int pos = 0; scanf(" %d",&pos); jousei[pos] = true; } for (int i = 0; i <= n*m*2; i++) { dansei[i%n] = dansei[i%n] || jousei[i%m]; jousei[i%m] = dansei[i%n] || jousei[i%m]; } for (int i = 0; i < n; i++) { if (!dansei[i]) { cout << "No" << endl; return 0; } } for (int i = 0; i < m; i++) { if (!jousei[i]) { cout << "No" << endl; return 0; } } cout << "Yes" << endl; return 0; } |
数学：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
#include<iostream> #include<cstring> #include<vector> #include<algorithm> using namespace std; int gcd(int a,int b){ return b == 0 ? a : gcd(b,a%b); } int main(){ int n,m; int boy; bool happy[101]; memset(happy, false, sizeof happy); int girl; cin>>n>>m; int d = gcd(n, m),k; cin>>boy; for(int i=0; i<boy; i++){ cin>>k; happy[k % d] = true; } cin>>girl; for(int i=0; i<girl; i++){ cin>>k; happy[k % d] = true; } for(int i=0; i<d; i++) if(happy[i] == false){ cout<<"No"<<endl; return 0; } cout<<"Yes"<<endl; return 0; } |
