flavius_map.cpp

Ulm大学2005-2006年竞赛题

#include <stdio.h>
#include <assert.h>
#include <map>
using namespace std;

int next(long long cur, long long a, long long b, long long n) {
	return (a*((cur*cur)%n)+b)%n;
}

int main() {
	freopen("flavius.in","r",stdin);
	int n,a,b;
	while(scanf("%d",&n) == 1 && n != 0) {
		assert(n >= 2 && n <= 1000000000);
		assert(scanf("%d %d",&a,&b) == 2);
		assert(a >= 0 && a < n && b >= 0 && b < n);
		int v = 0, len = 0;
		map<int,int> when;
		when[0] = 0;
		for (int i=1; 1; i++) {
			assert(i < 1000000);
			v = next(v,a,b,n);
			if (when.find(v) != when.end()) {
				len = i-when[v];
				break;
			}
			when[v] = i;
		}
		printf("%d\n",n-len);
	}
	return 0;
}