自动搬运

查看原文

来自洛谷，原作者为

	Tiw_Air_OAO 定义。专注。存在。

搬运于2025-08-24 22:28:48，当前版本为作者最后更新于2021-02-07 19:08:39，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

分享一个（自认为）比较简单的做法：

先特判 $a = 0$ 与 $b = 0$ 的情况。

定义 $f_n$ 为第 $n$ 个斐波那契数（这里取 $f_0 = 0, f_1 = 1$），则题目等价于 $af_{n-1} + bf_n = 0\bmod m$。

关于这一点，可以考虑 “转移矩阵中的值总可以写成斐波那契数”，那么第 $n$ 项即 $af_{n-1} + bf_n = 0\bmod m$。

一个自然的想法是变成 $-\frac{a}{b}=\frac{f_n}{f_{n-1}} \bmod m$，然而由于 $m$ 可以是合数，所以不一定互质。

考虑移项，并给 $a, b, m$ 同时除掉 $\gcd(a, b, m)$，得到：

注意此时 $\gcd(a', m')$ 仍可以 $> 1$。

由于 $\gcd(f_{n-1}, f_n) = 1$，此时应有 $\gcd(f_n, m') = \gcd(a',m') = p$ 以及 $\gcd(f_{n-1},m') = \gcd(b',m') = q$。

且此时等式两边以及模数同除 $pq$ 即可实现互质。

那么在 $m'$ 处塞个三元组 $(p,q,\frac{f_n}{f_{n-1}}\bmod \frac{m'}{pq})$，用 std::map 或 hash 维护，之后直接查询即可。

斐波那契数的循环节是 $O(n)$ 的（可以百度得到更进一步的分析）。

那么该算法预处理的复杂度为 $O(\sigma(m)\times \log m)$，其中 $\sigma(m)$ 是因子和，查询的复杂度是 $O(n\log m)$。

我的代码实现用的是 std::map，因此跑得比较慢。如果用 hash 可能会快一点。

#include <bits/stdc++.h>

const int N = 200000;

int gcd(int x, int y) {return (y == 0) ? x : gcd(y, x % y);}
void exgcd(int a, int b, int &x, int &y) {
	if( a == 1 ) {x = 1, y = 0;}
	else exgcd(b, a % b, y, x), y -= a / b * x;
}
int inv(int a, int m) {
	int x, y; exgcd(a, m, x, y);
	return (x % m + m) % m;
}

struct node{
	int x, y, z;
	friend bool operator < (const node &a, const node &b) {
		return (a.x == b.x) ? ((a.y == b.y) ? (a.z < b.z) : (a.y < b.y)) : (a.x < b.x);
	}
};

int m; std::map<node, int>mp[N + 5];
void init() {
	for(int i=2;i<=m;i++) if( m % i == 0 ) {
		int x = 1, y = 0;
		for(int j=0;;j++) {
			if( x && y ) {
				int d1 = gcd(i, x), d2 = gcd(i, y), m1 = i / d1 / d2;
				int k = (int)(1ll * (y / d2) * inv((x / d1), m1) % m1);
				if( !mp[i].count((node){k, d1, d2}) ) mp[i][(node){k, d1, d2}] = j;
			}
			int x1 = x; x = y, y = (x1 + y) % i;
			if( x == 1 && y == 0 ) break;
		}
	}
}

int main() {
//	freopen("fib.in", "r", stdin);
//	freopen("fib.out", "w", stdout);
	
	int n; scanf("%d%d", &n, &m), init();
	
	for(int i=1,a,b;i<=n;i++) {
		scanf("%d%d", &a, &b), b = (m - b) % m;
		
		if( a == 0 ) {puts("0"); continue;}
		if( b == 0 ) {puts("1"); continue;}
		
		int d = gcd(gcd(a, b), m), m1 = m / d; a /= d, b /= d;
		int p = gcd(a, m1), q = gcd(b, m1), m2 = m1 / p / q; a /= p, b /= q;
		
		int k = (int)(1ll * a * inv(b, m2) % m2);
		
		if( mp[m1].count((node){k, q, p}) ) printf("%d\n", mp[m1][(node){k, q, p}]);
		else printf("-1\n");
	}
}