Codeforces - 1010C

数学结论题 - 数论

题意：给定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;
}