2939.txt

来自「北大ACM题目例程 详细的解答过程 程序实现 算法分析」· 文本 代码 · 共 58 行

Problem Id:2939  User Id:fzk 
Memory:39688K  Time:1281MS
Language:G++  Result:Accepted

Source 

#include <algorithm>
#include <cstdio>
#include <string.h>
#include <map>
#include <stack>
#include <memory.h>
#include <math.h>
#include <queue>
using namespace std;
#define count dofudf
const int prime = 3374521;
int hash[prime] = { 0 };
int num[prime];
int id[prime];
int count = 0;

int get( int x ) {
	int y = x%prime;
	while( hash[y] == count && num[y] != x ) {
		y++;
		if( y == prime )
			y = 0;
	}
	return y;
}
		

int main( ) {
	int a, b, n, i, k;
	long long x;

	while( scanf( "%d%d%d", &n, &a, &b ) == 3 ) {
		if( n < 0 )
			break;
		x = 0;
		count++;
		i = 0;
		a%=n, b%=n;
		while( hash[k=get(int(x))] < count ){
			num[k] = x;
			id[k] = i;
			hash[k] = count;
			x = (a*x%n*x+b) % n;
			i++;
		}
		printf( "%d\n", n-(i-id[k]) );
	}
	return 0;
}