题目大意
求
$$
\sum_{i=1}^n\sum_{j=1}^mgcd(Fib_i,Fib_j)
$$
有人提出了神奇的解法。
注意到一个式子：
$$
Fib_a\times Fib_b+Fib_{a+1}\times Fib_{b+1}=Fib_{a+b+1}
$$
那么我们就有一个非常interesting的结论了：
$$
\begin{align*}
gcd(Fib_i,Fib_j)&=gcd(Fib_j\times Fib_{i-j+1}+Fib_{j-1}\times Fib_{i-j},Fib_j)\\
&=gcd(Fib_{i-1}\times Fib_{j-1},Fib_j)\\
&=Fib_{gcd(i,j)}
\end{align*}
$$
然后怎么利用莫比乌斯反演呢？
记$f(k)$为$gcd(i,j)=k$的$(i,j)$的对数，$g(k)$表示$k|gcd(i,j)$的$i,j$对数。
然后推式子：
$$
\begin{align*}
Ans&=\sum_{k=1}^n f(k)\times Fib_k\\
&=\sum_{k=1}^n Fib_k\times \sum_{k’|d}\mu(\frac{d}{k’})\times g(d)\\
&=\sum_{k=1}^n Fib_k\times \sum_{k’|d}\mu(\frac{d}{k’})\times \lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor
\end{align*}
$$
然后上板子吧。
latex挂了大家自求多福吧
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| #define REP(i, s, e) for (register int i = s; i <= e ;i++)
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e6 + 10, MOD = 1e9 + 7;
int m, n, k;
bitset <maxn> notprime;
int p[maxn], x[maxn], p_cnt;
int fib[maxn], u[maxn], ans;
inline int mod(int x) {return x >= MOD ? x - MOD : x;}
int main()
{
#ifndef ONLINE_JUDGE
freopen("B.in", "r", stdin);
freopen("B.out", "w", stdout);
#endif
cin >> n >> m;
REP(i, 2, n)
{
if (!notprime[i]) x[p[++p_cnt] = i] = i;
REP(j, 1, p_cnt)
{
if (i * p[j] > n) break;
notprime[i * p[j]] = 1;
x[i * p[j]] = p[j];
if (i % p[j] == 0) break;
}
}
fib[1] = 1;
REP(i, 2, n) fib[i] = mod(fib[i-1] + fib[i-2]);
u[1] = 1;
REP(i, 2, n)
if (x[i] ^ x[i / x[i]]) u[i] = -u[i / x[i]];
REP(i, 1, n)
for (register int j = 1; i * j <= n; j++)
ans += 1ll * u[j] * (n / i / j) * (m / i / j) % MOD * fib[i] % MOD, ans %= MOD;
cout << (ans + MOD) % MOD << endl;
return 0;
}
|
