pku2381.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

/*
	Author:Sempr
	Algorithm:暴力
	Date:2005-05-03
*/

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

const int size = 16000001;
int a, c, m, R;
int cnt;
int st[size / 32];

bool Insert(int x)
{
	if (st[x / 32] & (1 << (x % 32)))
	{
		return 0;
	}
	st[x / 32] |= 1 << (x % 32);
	return 1;
}

bool Judge(int x)
{
	return st[x / 32] & (1 << (x % 32));
}

void Solve()
{
	int i, max, l;
	cnt = 1;
	memset(st, 0, sizeof(st[0]) * (m / 32 + 1));
	Insert(R);
	for (i = 1; 1; i++)
	{
		R = (a * R + c) % m;
		if (!Insert(R))
		{
			break;
		}
	}
	max = 0;
	for (i = 0; i < m; i++)
	{
		if (Judge(i))
		{
			l = i;
			break;
		}
	}
	for (i++; i < m; i++)
	{
		if (Judge(i))
		{
			if (max < i - l)
			{
				max = i - l;
			}
			l = i;
		}
	}
	printf("%d\n", max);
}


int main()
{
	while (scanf("%d %d %d %d", &a, &c, &m, &R) != -1)
	{
		Solve();
	}
	return 0;
}