首页 > 代码库 > SGU 181.X-Sequence

SGU 181.X-Sequence

2024-07-12 09:06:09   221人阅读

时间限制：0.5s

空间限制：4M

题意：

       令X0=A，

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

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

 

 

 

Solution:

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

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

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

 

code：

 

#include <iostream>#include <string>#include <cstring>#include <vector>using namespace std;const int INF = 111111;vector<int> ans;int f[INF];long long  x, a, b, c, m, k, t;inline long long  get (long long x) {	return (a * x * x  + b * x  + c) % m;}int main() {	cin >> x >> a >> b >> c >> m >> k;	//找到第一次循环结束的地方，即第二次循环开始的地方	for (t = 0; !f[x]; x = get (x), t++) {		f[x] = 1;		if (t == k) {			cout << x;			return 0;		}	}	k -= (t-1);//从循环起点算起的K的新位置     //得到循环数组	memset (f, 0, sizeof f);	for (t = 0; !f[x];) {		f[x] = 1;		ans.push_back (x);		x = get (x), t++;	}	//找到k在循环节里的位置并输出	k = k % t - 1;	if (k < 0) k = t - 1;	cout << ans[k];	return 0;}

 

　　


联系
我们