Codeforces #499 Div1 C. Border

これこそ750ptでもいい気がする。
http://codeforces.com/contest/1010/problem/C

問題

N種類の貨幣があり、それぞれの価値はA[i]である。
これらの貨幣を任意枚数合わせたとき、その価値のK進数における1の位は何通りの値を取れるか。

解法

G=GCD(K, A[0], A[1], .. , A[n-1])の倍数の値を取れるので、Gの倍数をK/G通り答えればよい。
先にA[i]にmod Kを取ったりすると結果が0となってややこしいがKとのGCDを順次取っていけばそんなこともない。

int N,K;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	x=K;
	FOR(i,N) {
		cin>>y;
		x=__gcd(x,y);
	}
	
	cout<<K/x<<endl;
	FOR(i,K/x) cout<<x*i<<" ";
	cout<<endl;
}

まとめ

意外と引っかかって落としてる人がいたのが予想外。