数学结论题 - 数论

题意:给定n个数Ai,一个整数k,每个数可以用任意次,求这些数的和模K之后有多少种可能,分别是哪些数

提交:http://codeforces.com/problemset/problem/1010/C

思路:从简到繁

(1)当存在某个Ai模K等于1时,那答案是K,从0到K-1都可以;

(2)当n个数模K都不是1,如果存在Ai % K = x,Ai % K = y,gcd(x,y) = 1,那么根据数论性质,由x和y可以构造出0 - K-1的任意数:x,x+y,x+2y,……,x+(k-1)y这些数在同余的意义下就是 0 - K-1

(3)若不存在(1)(2)中的情况,那么就是所有的Ai % K之后,再取上gcd,会等于一个数X,可知X是K的约数(可以利用反证,若gcd(X,K)=1,那么X,2X,3X,……,(K-1)X在同余意义下就是0 - K-1,和(2)相同了),那么结果为K/X

想明白了之后,三种情况就是一种,代码如下:

#include <iostream>
#include <stdio.h>
using namespace std;

int gcd(int a, int b){
    return a == 0 ? b : gcd(b%a, a);
}

int main(){
	int n,k,x;
	scanf("%d%d",&n,&k);
	int tmp = k;
	for(int i = 1;i <= n;i++){
		scanf("%d",&x);
		tmp = gcd(x%k,tmp);
	}
	printf("%d\n",k / tmp);
	for(int i = 0; i < k/tmp; i++)
		printf("%d%c",i * tmp, i == k/tmp - 1?'\n':' ');
	return 0;
}