[数据结构与算法]H . 真签到题

题目链接

题目描述

Fibonacci 数列，f(n)=f(n?1)+f(n?2)
前n项为1 1 2 3 5 8 …
给出n,m，需要你计算出满足条件的对数（i，j）的个数，且i<=j。
条件是：
1<=gcd(f(i)，f(j))<=n
i,j<=m
由于答案可能很大，所以对1e9+7取模

输入描述:

第一行为一个整数T，表示T组测试数据。
接下来共T行，每行为两个整数n,m。
1<=T<=1e5
1<=n<=1e18
1<=m<=1e6

输出描述:

输出满足条件的对数。

示例1

输入

2
5 5
4 4

输出

15
10

示例2

输入

3
1 6
3 2
3 1

输出

16
3
1

解决思路：

总结结论：
有关$Fibonacci$数的$gcd$的题目，需要了解一个公式，$gcd(f(n),f(m))=f(gcd(n,m))$

已知条件：
将题目中的要求写成公式形式。
即需要计算：$\sum _{g=1}^n\sum _{i=1}^m\sum _{j=i}^m[gcd(f(i),f(j))=g]$
这个公式的含义是：$g$枚举$gcd$的时候，看一下有多少对$(i,j)$满足条件。
应用上面的公式，转换一下为：$\sum _{g=1}^n\sum _{i=1}^m\sum _{j=i}^m[f(gcd(i,j))=g]$
观察上面的公式，会发现只有当$g$和$f(gcd(i,j))$相等时才会有贡献。
且$Fibonacci$增长很快，所以$g$的可能取值只有最小的$Fibonacci$数到小于等于n的最大的$Fibonacci$数。
因为正好取的是连续的$Fibonacci$数，所以$gcd(i,j)$的取值也是连续的。
设小于等于$n$的最大的$Fibonacci$数为$mx$,且是第$cnt$个$Fibonacci$数。
公式就可以转化为：$\sum _{g=1}^{cnt}\sum _{i=1}^m\sum _{j=i}^m[gcd(i,j)=g]$
需要计算的是$i\le j$的对数，会发现等价于$j\le i$的对数。
公式变为：$\sum _{g=1}^{cnt}\sum _{i=1}^m\sum _{j=1}^i[gcd(i,j)=g]$
$gcd(i,j)=g$意味着$i$和$j$都是$g$的倍数,所以对$i,j$除以$g$,变换枚举上限。
公式为：$\sum _{g=1}^{cnt}\sum _{i=1}^{?\frac{m}{g}?}\sum _{j=1}^i[gcd(i,j)=1]$
发现里面就是欧拉函数的形式了。
公式为：$\sum _{g=1}^{cnt}\sum _{i=1}^{?\frac{m}{g}?}\phi (i)$
$cnt$很小，里面就是欧拉函数的前缀和，直接预处理即可。
思路里程：
看到$Fibonacci$的最大公约数，就试着套用上面的公式求解，这个公式可以降低枚举范围，本来枚举的是$Fibonacci$的范围，降低之后只需要枚举下标的范围了。
对数个数计算的几种方法。
第一种：和文章中一样，如果可以交换顺序的话，就用那种容易计算的就行。
第二种：可以容斥计算，小于等于的个数等于随便取的个数加上相等的对数个数除以2。
实现过程：
需要暴力计算出$cnt$（小于等于$n$的最大的$Fibonacci$数的下标）
欧拉筛预处理欧拉函数，再对欧拉函数求前缀和。
取模时处处取模，防止溢出。

代码

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
#ifdef DOIDO_DEBUG
#define debug(x) cout<< #x << " --> " << (x) << "\n";
#define debug_pair(x, y) cout<< #x << " " << #y \
<< " --> " << (x) << " " << (y) << "\n";
#else
#define debug(x)
#define debug_pair(x, y)
#endif

#define endl '\n'
#define N   int(1e6 + 10)
#define MOD int(1e9 + 7)


int cnt;
int phi[N];
bool vis[N];
int prime[N];
ll pre_phi[N];

void init_prime(const int& n) {
	phi[1] = 1;
	for (int i = 2; i <= n; i++) {
		if (!vis[i]) {
			phi[i] = i - 1;
			prime[++cnt] = i;
		}
		for (int j = 1; i <= n / prime[j]; j++) {
			vis[i * prime[j]] = true;
			if (i % prime[j] == 0) {
				phi[i * prime[j]] = phi[i] * (prime[j]);
				break;
			}
			phi[i * prime[j]] = phi[i] * (prime[j] - 1);
		}
	}

	ll pre = 0;
	for (int i = 1; i <= n; i++) {
		// 处处取模，防止溢出
		pre_phi[i] = (pre_phi[i - 1] + phi[i]) % MOD;
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	// 预处理欧拉函数前缀和
	init_prime(1e6);

	// 计算Fibonacci数，大于最大值就跳出。
	static ll fi[N] = { 0, 1, 1 };
	for (int i = 3; i <= 100; i++) {
		fi[i] = fi[i - 1] + fi[i - 2];
		if (fi[i] > 1e18) break;
	}

	int T;
	cin >> T;

	for (int j = 1; j <= T; j++) {
		ll n, m;
		cin >> n >> m;

		int pos = 0;
		for (int k = 1; k <= 100; k++) {
			if (fi[k] > n) {
				pos = k;
				// 找到大于n的位置跳出即可。
				break;
			}
		}
		// 由于找的是大于n的最小位置，所以需要位置减一
		pos--;

		ll ans = 0;
		for (int g = 1; g <= pos; g++) {
			ans = (ans + pre_phi[m / g]) % MOD;
		}
		cout << ans << endl;
	}
	return 0;
}