DCOJ5117 set

题目描述

给定一个数集 A，要求构造一个数集 B，满足：

• 对于 A 集合中任意的数 x，x 属于 B，即 A ⊆ B；

• 对于 B 集合中任意的数 a, b，(a + b) mod p 属于 B，其中 p 是一个给定的正整数。求 B 的大小的最小值。

输入格式

第一行两个整数 n, p，其中 n 为 A 的大小。

第二行 n 个整数，表示数集 A 中的数，保证这些数都在 [0, p − 1] 内，保证这些数两两不同。

输出格式

一个整数，表示答案。

样例

####样例输入

2 10

4 6

####样例输出

5



一道2分钟AC的gcd裸题。其实就是找满足k₁*x₁+k₂*x₂+...+k_n*x_n≡f(mod p)的f有多少个，然后可以直接算t=gcd(x₁,x₂,...,x_n,p)，所有t的倍数的f(f<p且f可以为0)都可以得到

//Serene

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

#include<cmath>

using namespace std;

const int maxn=1e5+10;

int n,p,a[maxn];

int aa;char cc;

int read() {

	aa=0;cc=getchar();

	while(cc<'0'||cc>'9') cc=getchar();

	while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();

	return aa;

}

int gcd(int x,int y) {

	return y? gcd(y,x%y):x;

}

int main() {

	n=read();p=read();

	for(int i=1;i<=n;++i) if(i>1)a[i]=gcd(a[i-1],read());else a[i]=read();

	a[n]=gcd(a[n],p);

	printf("%d",p/a[n]);

	return 0;

}

巴特西

DCOJ5117 set

题目描述

输入格式

输出格式

样例

最新文章

热门文章