题解 P3306 [SDOI2013] 随机数生成器

标签：return int 题解 生成器 rest pmod SDOI2013 equiv Mod

Link

它 \(p\) 都是质数了，这不就明示我们是 bsgs 了吗

我没看出来

然后我们来倒一下 \(n\) 天的式子

第一天是 \(x_1\)，第二天是 \(ax_1+b\)，第三天是 \(a^2x_1+(ab+b)\)，第四天是 \(a^3x_1 +(a^2b+ab+b)\)。

我们一通大眼观察，观察出来第 \(n\) 天是 \(a^{n - 1}x_1+\sum\limits_{i = 0}^{n-2}a^ib\)。

然后由于我学艺不精赶紧滚回幼儿园重读！没有想到等比数列求和二年级小朋友 QAQ，我们拿等比数列求和公式往右边一套，就是 \(a^{n-1}x_1+\dfrac{(a^{n - 1} - 1)b}{a-1}\equiv t \pmod p\)

两边同时乘上 \(a - 1\)，那么 \((a-1)a^{n - 1}x_1 + (a^{n - 1} - 1) b\equiv (a - 1)t\pmod p\)

我们不知道 \(n - 1\)，\(n - 1\) 在指数位置上，我们考虑 BSGS，我们考虑把 \(a^{n-1}\) 给单独搞出来，左边化简得到 \((ax_1 - x_1+b)a^{n - 1} - b\equiv (a-1)t\pmod p\)

移项得到 \(a^{n - 1}\equiv \dfrac{(a-1)t + b}{ax_1 - x_1 + b} \pmod p\)。

好，BSGS 板子一套即可……吗？

---

全 T 了……离谱……

然后把数据一下，我们定睛一看，就会发现这样一个事情

有一些比较搞基的情况

1. \(x_1 = 1\) 输出 \(1\) 即可。
2. \(a = 0\)
   如果 \(t = b\)，输出 \(2\)（第一天 \(x_1\)，第二天 \(0 +b = b\)），否则输出 \(-1\)。
3. \(a = 1\)。
   这个时候 \(x_n = x_1 + (n - 1)b\)。
   所以 \(x_1+(n-1)b\equiv t\pmod p\)，战术移项一下 \((n - 1) \equiv (t - x_1)b^{-1}\pmod p\)

代码

一定要开 longlong！

//SIXIANG
#include <iostream>
#include <cmath>
#include <map>
#define MAXN 100000
#define int long long
#define QWQ cout << "QWQ" << endl;
using namespace std;
map <int, int> M;
int pp, a, b, x1, t;
int exgcd(int a, int b, int &x, int &y) {
	if(!b) {x = 1, y = 0; return a;}
	else {
		int rest = exgcd(b, a % b, x, y);
		int tmp = x; x = y, y = tmp - a / b * y;
		return rest;
	}
} 
int qmul(int n, int m, int Mod) {
	int rest = 0;
	while(m) {
		if(m & 1) rest = ((rest + n) % Mod + Mod) % Mod;
		m >>= 1, n = ((n + n) % Mod + Mod) % Mod;
	}
	return rest;
}
int qpow(int n, int m, int Mod) {
	int rest = 1;
	while(m) {
		if(m & 1) rest = qmul(rest, n, Mod) % Mod;
		m >>= 1, n = qmul(n, n, Mod) % Mod;
	}
	return rest;
}

void BSGS(int a, int b, int m) {
	int t = ceil(sqrt(m)), qwq = b % m, qaq = 1, quq = 1;
	M[qwq] = 0;
	for(int p = 1; p <= t; p++) {
		qwq = qwq * a % m;
		M[qwq] = p;
	}
	qaq = qpow(a, t, m);
	for(int p = 1; p <= t; p++) {
		quq = quq * qaq % m;
		if(M[quq]) {
			cout << ((p * t - M[quq]) % m + m) % m + 1 << endl;
			return ;
		}
	}
	cout << -1 << endl;
}
void get() {
	M.clear();
	if(t == x1) {
		cout << 1 << endl;
		return ;
	} 
	if(a == 0) {
		if(t == b) cout << 2 << endl;
		else cout << -1 << endl;
		return ;
	}
	if(a == 1) {
		if(!b) {
			cout << -1 << endl;
			return ;
		}
		int rt = (t - x1); 
		rt = (qmul(rt, (qpow(b, pp - 2, pp)), pp));
		cout << ((rt % pp) + pp) % pp + 1 << endl;
		return ;
	}
	
	int A = qmul(((a - 1) % pp + pp) % pp, t, pp);
	int B = qmul(a, x1, pp);
	int m = qmul((A + b), qpow(((B - x1 + b) % pp + pp) % pp, pp - 2, pp), pp);

	if((A + b) % pp == 0) cout << -1 << endl;
	else BSGS(a, m, pp);
}
void init() {
	cin >> pp >> a >> b >> x1 >> t;
	get();
}
signed main() {
	int T; cin >> T;
	while(T--)
		init();
}

标签：return,int,题解,生成器,rest,pmod,SDOI2013,equiv,Mod
From： https://www.cnblogs.com/thirty-two/p/17208514.html