uva 408 - Uniform Generator

第一感觉，step跟mod的最大公约数应该为1，这样就满足了，尝试了一下，AC，但是不懂解释，钥匙比赛能有这感觉多好。。

#include <stdio.h>
int gcd(int a, int b) {
	return b == 0 ? a : gcd(b, a % b);
}
int main() {
	int step, mod;
	while(~scanf("%d%d", &step, &mod)) {
		printf("%10d%10d    ", step, mod);
		if(gcd(step, mod) == 1) printf("Good Choice/n/n");
		else printf("Bad Choice/n/n");
	}
	return 0;
}

其实数据量不大，枚举也能过。

#include <stdio.h>
#include <string.h>
bool isVis[100001];
int gcd(int a, int b) {
	return b == 0 ? a : gcd(b, a % b);
}
int main() {
	int step, mod;
	while(~scanf("%d%d", &step, &mod)) {
		printf("%10d%10d    ", step, mod);
		memset(isVis, false, sizeof(isVis));
		isVis[0] = true;
		int seed = 0;
		int count = 1;
		while(true) {
			int tmp = (seed + step) % mod;
			if(isVis[tmp]) break;
			count++;
			isVis[tmp] = true;
			seed = tmp;
		}
		if(count == mod) printf("Good Choice/n/n");
		else printf("Bad Choice/n/n");
	}
	return 0;
}