题目链接
题目描述
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
解决思路：
总结结论：
有关
F
i
b
o
n
a
c
c
i
Fibonacci
Fibonacci数的
g
c
d
gcd
gcd的题目，需要了解一个公式，
g
c
d
(
f
(
n
)
,
f
(
m
)
)
=
f
(
g
c
d
(
n
,
m
)
)
gcd(f(n),f(m))=f(gcd(n,m))
gcd(f(n),f(m))=f(gcd(n,m))
已知条件：
将题目中的要求写成公式形式。
即需要计算：
∑
g
=
1
n
∑
i
=
1
m
∑
j
=
i
m
[
g
c
d
(
f
(
i
)
,
f
(
j
)
)
=
g
]
\sum\limits_{g=1}^{n}\sum\limits_{i=1}^{m}\sum\limits_{j=i}^{m}[gcd(f(i),f(j))=g]
g=1∑ni=1∑mj=i∑m[gcd(f(i),f(j))=g]
这个公式的含义是：
g
g
g枚举
g
c
d
gcd
gcd的时候，看一下有多少对
(
i
,
j
)
(i,j)
(i,j)满足条件。
应用上面的公式，转换一下为：
∑
g
=
1
n
∑
i
=
1
m
∑
j
=
i
m
[
f
(
g
c
d
(
i
,
j
)
)
=
g
]
\sum\limits_{g=1}^{n}\sum\limits_{i=1}^{m}\sum\limits_{j=i}^{m}[f(gcd(i,j))=g]
g=1∑ni=1∑mj=i∑m[f(gcd(i,j))=g]
观察上面的公式，会发现只有当
g
g
g和
f
(
g
c
d
(
i
,
j
)
)
f(gcd(i,j))
f(gcd(i,j))相等时才会有贡献。
且
F
i
b
o
n
a
c
c
i
Fibonacci
Fibonacci增长很快，所以
g
g
g的可能取值只有最小的
F
i
b
o
n
a
c
c
i
Fibonacci
Fibonacci数到小于等于n的最大的
F
i
b
o
n
a
c
c
i
Fibonacci
Fibonacci数。
因为正好取的是连续的
F
i
b
o
n
a
c
c
i
Fibonacci
Fibonacci数，所以
g
c
d
(
i
,
j
)
gcd(i,j)
gcd(i,j)的取值也是连续的。
设小于等于
n
n
n的最大的
F
i
b
o
n
a
c
c
i
Fibonacci
Fibonacci数为
m
x
mx
mx,且是第
c
n
t
cnt
cnt个
F
i
b
o
n
a
c
c
i
Fibonacci
Fibonacci数。
公式就可以转化为：
∑
g
=
1
c
n
t
∑
i
=
1
m
∑
j
=
i
m
[
g
c
d
(
i
,
j
)
=
g
]
\sum\limits_{g=1}^{cnt}\sum\limits_{i=1}^{m}\sum\limits_{j=i}^{m}[gcd(i,j)=g]
g=1∑cnti=1∑mj=i∑m[gcd(i,j)=g]
需要计算的是
i
≤
j
i \le j
i≤j的对数，会发现等价于
j
≤
i
j \le i
j≤i的对数。
公式变为：
∑
g
=
1
c
n
t
∑
i
=
1
m
∑
j
=
1
i
[
g
c
d
(
i
,
j
)
=
g
]
\sum\limits_{g=1}^{cnt}\sum\limits_{i=1}^{m}\sum\limits_{j=1}^{i}[gcd(i,j)=g]
g=1∑cnti=1∑mj=1∑i[gcd(i,j)=g]
g
c
d
(
i
,
j
)
=
g
gcd(i,j)=g
gcd(i,j)=g意味着
i
i
i和
j
j
j都是
g
g
g的倍数,所以对
i
,
j
i,j
i,j除以
g
g
g,变换枚举上限。
公式为：
∑
g
=
1
c
n
t
∑
i
=
1
⌊
m
g
⌋
∑
j
=
1
i
[
g
c
d
(
i
,
j
)
=
1
]
\sum\limits_{g=1}^{cnt}\sum\limits_{i=1}^{\left \lfloor \frac{m}{g}\right \rfloor}\sum\limits_{j=1}^{i}[gcd(i,j)=1]
g=1∑cnti=1∑⌊gm⌋j=1∑i[gcd(i,j)=1]
发现里面就是欧拉函数的形式了。
公式为：
∑
g
=
1
c
n
t
∑
i
=
1
⌊
m
g
⌋
φ
(
i
)
\sum\limits_{g=1}^{cnt}\sum\limits_{i=1}^{\left \lfloor \frac{m}{g}\right \rfloor}\varphi (i)
g=1∑cnti=1∑⌊gm⌋φ(i)
c
n
t
cnt
cnt很小，里面就是欧拉函数的前缀和，直接预处理即可。
思路里程：
看到
F
i
b
o
n
a
c
c
i
Fibonacci
Fibonacci的最大公约数，就试着套用上面的公式求解，这个公式可以降低枚举范围，本来枚举的是
F
i
b
o
n
a
c
c
i
Fibonacci
Fibonacci的范围，降低之后只需要枚举下标的范围了。
对数个数计算的几种方法。
第一种：和文章中一样，如果可以交换顺序的话，就用那种容易计算的就行。
第二种：可以容斥计算，小于等于的个数等于随便取的个数加上相等的对数个数除以2。
实现过程：
需要暴力计算出
c
n
t
cnt
cnt（小于等于
n
n
n的最大的
F
i
b
o
n
a
c
c
i
Fibonacci
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;
}
