Let {x
i} be the infinite sequence of integers:
1) x
0 = 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.
一开始想求出递推式，结果求不出来。。。
不过由于式子是mod M(1<=M<=1000)，所以xi不同的值最多只有1000个，不算x0，所以至多计算1000次。
定义一个数组存储Xi,另一个数组帮助判断Xi从哪个值开始循环。
WA on 39: ans[0]应该设为A%m, 由于flag[A%m]设为0，所以如果x1算出来是A%m，程序会认为已经和x0重复，而x0是A而不是A%m会出错。另外可以设为A%m的原因是，X1=f(x0)=f(x0%m)
#include <stdio.h>
#include <string.h>
int main(void) {
int A, a, b, c, m, k;
scanf ("%d%d%d%d%d%d", &A, &a, &b, &c, &m, &k);
int ans[1000] = {A%m};
int flag[1001];
memset(flag, -1, sizeof(int)*1001);
flag[A%m]=0;
int i;
for (i = 1; flag[ans[i]=(a*ans[i-1]*ans[i-1]+b*ans[i-1]+c)%m]<0; ++i) {
flag[ans[i]] = i;
}
if (k==0) {
printf ("%d\n", A);
} else if (k >= flag[ans[i]]) {
printf ("%d\n", ans[(k-flag[ans[i]])%(i-flag[ans[i]])+flag[ans[i]]]);
} else {
printf ("%d\n", ans[k]);
}
return 0;
}