高端网站策划公司/网店运营推广平台

判断子群

Time Limit: 1000 ms Memory Limit: 65536 KiB

Submit Statistic

Problem Description

给定一个有限群S，和他的一个子集S1，定义S上的二元运算*为模M加法运算，判断该子集是否为S的子群。（子群的定义：设H为群G的非空子集。如果H在G的运算下构成群，则称H为G的子群）

Input

多组输入，第一行为有限群S的元素个数n(0<=n<100)，数M(0<=M<100)，其子集的元素个数m(0<=m<100)（元素可能有重复）
第二行n个数为有限群含有的元素x(0 <= x < 100)，第三行m个数为子集含有的元素y(0 <= y < 100)。
输出
如果该子集是S的子群输出“YES”，反之输出“NO”（不含引号）

Output

如果该子集是S的子群输出“YES”，反之输出“NO”（不含引号）

Sample Input

8 7 7
0 1 2 3 4 5 6 6
0 1 2 3 4 5 6
10 7 7
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 9

Sample Output

YES
NO

Hint

Source

fhf-xry

/*** 题目中已说s是有限群 所有不必管s的数据只要判定s1是否构成群即可*/
#include <bits/stdc++.h>
using namespace std;
int arr[111];  // 存放群s的数据
int brr[111];  // 存放群s1数据
int num[111];  // 存放群s1内元素的逆元（不存在逆元 就不能构成群）
int main() {int n, m, q;while (cin >> n >> m >> q) {int flag = 0;memset(num, -1, sizeof(num));for (int i = 1; i <= n; i++) {cin >> arr[i];}for (int i = 1; i <= q; i++) {cin >> brr[i];if (brr[i] == 0) flag = 1;  // 要想s1是群   0必须存在}num[0] = 0;  // 0的逆元是0for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {// 在群中找每个元素的逆元  即 元素i 和 元素j 都在群中 且// i+j%m==0if (flag && (brr[i] + brr[j]) % m == 0) {num[brr[i]] = brr[j];num[brr[j]] = brr[i];break;}}}for (int i = 1; i <= n; i++) {if (num[brr[i]] == -1) {  // 要想成群  每个元素都有逆元flag = 0;}}printf(flag == 0 ? "NO\n" : "YES\n");}return 0;
}