SGU 181 X-Sequence(一题比较水的求模找规律)

E - X-Sequence

Time Limit:500MS Memory Limit:4096KB 64bit IO Format:%I64d
& %I64u

Description

Let {x_i} be the infinite sequence of integers:

1) x₀ = A;

2) x_i = (alpha * x_i-1^2 + beta * x_i-1 + gamma) mod M, for i >= 1.

Your task is to find x_k if you know A, alpha, beta, gamma, M and k.

Input

Given A (1 <= A <= 10000), alpha (0 <= alpha <= 100), beta (0 <= beta <= 100), gamma (0 <= gamma <= 100), M (1 <= M <= 1000), k (0 <= k <= 10^9). All numbers are integer.

Output

Write x_k.

Sample Input

Input

1 1 1 1 10 1

Output

题意：

令X₀=_A，

X_i=(a*X_i-1^{^2}，b*X_i-1+c)%m;

求X_k,(0<=k<=109),(0<=a,b<=100),(1<m<1000);

Solution:

题目的关键在于m的范围，1000的范围显然是会在取余后出现循环的。

只要得出循环的数列的长度以及它的每一个数，和任意一个循环的起点位置。就可以算出X_k值。

要注意的是X₀是不对m取余的，还有当X₀很大时，计算X₁的中间量是有可能超过int范围的。

code：

#include<stdio.h>

#include<string.h>

int main()

{

	int A, alpha, beta, gamma, M , k;

	int loop,i,t;

	int num[1010];

	int visit[10100];//注意这里要开10000+虽然用的个数不超过1000个只是因为A<=10000

	//visit用来标记是否num[i]的值是否出现过即visit[num[i]]是否是-1

	//因为M<1000 所以会在至多1000个数开始出现循环

	while(~scanf("%d%d%d%d%d%d",&A,&alpha,&beta,&gamma,&M,&k))

	{

		memset(visit,-1,sizeof(visit));

		num[0]=A;visit[A]=0;

		for(i=1;;i++)

		{

			num[i]=alpha*num[i-1]%M*num[i-1]%M+beta*num[i-1]%M+gamma%M;

			num[i]%=M;

			if(visit[num[i]]!=-1){

		/*	loop=i; //i 个开始出现循环       k(i)(visit[num[i]])=  0 1 2 3 4 5 6 7

		   注意这里这样是错的, 它循环可能是中间出现循环如 (num[i]) 9 7 8 4 5 6 8 4  (6-2)

		   所以这样记录的个数不是i个, 固修改如下

		*/

				loop=i-visit[num[i]]; //这样loop正好为循环个数

				t=visit[num[i]];//表示循环列前面还有的个数

			break;

			}

			else visit[num[i]]=i; //

		}

		if(k<visit[num[i]])printf("%d\n",num[k]); //如果k未出现循环

		else printf("%d\n",num[(k-t)%loop+t]);

	}

	return 0;

}