Go语言视频零基础入门到精通

admin

题目链接
简单的数学题
题目描述
输入一个整数n和一个整数p，你需要求出
\[\sum_{i=1}^n\sum_{j=1}^n (i\cdot j\cdot gcd(i,j))\ mod\ p\]
其中\(gcd(a,b)\)表示\(a\)与\(b\)的最大公约数
输入
一行两个整数\(p,n\)
输出
一行一个整数，为题目中所求值
样例
样例输入

1. [code]998244353 2000

复制代码

[/code]

样例输出

1. [code]883968974

复制代码

[/code]

数据范围
\(n\leq 10^{10}\)
\(5\times 10^8 \leq p \leq 1.1\times 10^9​\)
\(p​\)为质数（但貌似也可以不是？又不用求逆元）
题解
自己想出来的题！但是连\(WA\)两发就是因为杜教筛写挂了……
先不考虑取余，我们化一下题目中的式子，枚举\(gcd\)（警告！多公式）。
\[\sum_{i=1}^n\sum_{j=1}^n i\cdot j\cdot gcd(i,j)\]
\[\sum_{d=1}^{n}d\sum_{i=1}^{\left\lfloor \frac{n}{d}\right\rfloor}\sum_{j=1}^{\left\lfloor \frac{n}{d}\right\rfloor}[i\perp j]i\cdot j \cdot d^2\]
\[\sum_{d=1}^{n}d^3\sum_{i=1}^{\left \lfloor \frac{n}{d}\right\rfloor}\sum_{j=1}^{\left\lfloor \frac{n}{d}\right\rfloor}[i\perp j]i\cdot j\]
\[\sum_{d=1}^{n}d^3\sum_{p=1}^{\left \lfloor \frac{n}{d}\right\rfloor}\mu(p)p^2\cdot \Big(\frac{(1+\left\lfloor \frac{n}{dp}\right\rfloor)\left\lfloor \frac{n}{dp}\right\rfloor}{2}\Big)^2\]
额，现在可以使用分块优化做到\(O(n)​\)了，但是这完全不能胜任数据范围，我们换个角度，设\(dp=T​\)，枚举T会有什么结果？
\[\sum_{T=1}^{n}\Big(\frac{(1+\left\lfloor \frac{n}{T}\right\rfloor)\left\lfloor \frac{n}{T}\right\rfloor}{2}\Big)^2\sum_{d|T}d^3\cdot \mu(\frac{T}{d})(\frac{T}{d})^2\]
\[\sum_{T=1}^{n}\Big(\frac{(1+\left\lfloor \frac{n}{T}\right\rfloor)\left\lfloor \frac{n}{T}\right\rfloor}{2}\Big)^2 T^2\sum_{d|T}d\cdot \mu(\frac{T}{d})\]
现在好像反而变成\(O(n\log n)\)或\(O(n\sqrt{n})\)了，别急，我们看看第二层的求和的意义——狄利克雷卷积，这是\(Id\)函数与\(\mu\)函数的狄利克雷卷积，其值就等于\(\varphi\)。
\[\sum_{T=1}^{n}\Big(\frac{(1+\left\lfloor \frac{n}{T}\right\rfloor)\left\lfloor \frac{n}{T}\right\rfloor}{2}\Big)^2 T^2\varphi(T)\]
现在，我们只需要快速求出一个东西即可——\(T^2\varphi(T)\)，前面的部分可以分块优化，我们急需解决的就是这个函数\(f(T)=T^2\varphi(T)\)的前缀和\(F(T)\)。显然，这是一个积性函数。
杜教筛的公式：
\[\sum_{i=1}^{n}(f*g)(i)=\sum_{i=1}^{n}\sum_{d|i}f(d)\cdot g(\frac{i}{d})=\sum_{i=1}^{n}g(i)\sum_{j=1}^{\left\lfloor \frac{n}{i}\right\rfloor}f(j)\]
于是我们需要一个函数与\(f\)卷起来，我们根据套路或枚举发现\(T^2\)项很恼人，于是尝试把这一项消掉，于是想到了\(g(x)=x^2\)。
\[\sum_{i=1}^{n}\sum_{d|i}d^2\varphi(d)\cdot (\frac{i}{d})^2=\sum_{i=1}^{n}i^2\sum_{j=1}^{\left\lfloor \frac{n}{i}\right\rfloor}f(j)\]
\[\sum_{i=1}^{n}i^2\sum_{d|i}\varphi(d)=\sum_{i=1}^{n}i^2F(\left\lfloor \frac{n}{i}\right\rfloor)​\]
根据公式\(\sum_{d|i}\varphi(d)=i\)，继续变形
\[\sum_{i=1}^{n}i^3=F(n)+\sum_{i=2}^{n}i^2F(\left\lfloor \frac{n}{i}\right\rfloor)\]
\[F(n)=\sum_{i=1}^{n}i^3-\sum_{i=2}^{n}i^2F(\left\lfloor \frac{n}{i}\right\rfloor)\]
由于\(p(i)=i^3\)和\(q(i)=i^2\)的前缀和都有公式，我们可以对右边进行分块优化，就可以杜教筛了！这道题圆满解决，时间复杂度\(O(n^{\frac{2}{3}})\)。
不过有些小细节要注意，比如模数乘\(2\)可能会爆\(int\)，\(n^2\)可能会爆\(long\ long\)，需要先取模再平方
\(Code:\)

1. [code]#include <map>
2. #include <cstdio>
3. #include <cstring>
4. #include <iostream>
5. #include <algorithm>
6. using namespace std;
7. #define N 5000005
8. #define ll long long
9. map<ll, ll>Phi;
10. ll n, mod, g[N];
11. int p[N], h[N], phi[N], cnt;
12. ll sqr(ll x)
13. {
14.     ll a = 2 * x + 1, b = x + 1, c = x;
15.     if (b % 2 == 0)b /= 2;
16.     else c /= 2;
17.     if (a % 3 == 0)a /= 3;
18.     else
19.         if (b % 3 == 0)b /= 3;
20.         else c /= 3;
21.     a %= mod, b %= mod, c %= mod;
22.     return a * b % mod * c % mod;
23. }
24. ll seq(ll x)
25. {
26.     ll a = x + 1, b = x;
27.     if (a % 2 == 0)a /= 2;
28.     else b /= 2;
29.     a %= mod, b %= mod;
30.     return a * b % mod;
31. }
32. ll vas(ll x)
33. {
34.     ll a = seq(x);
35.     return a * a % mod;
36. }
37. ll G(ll x)
38. {
39.     if (x <= N - 5)
40.         return g[int(x)];
41.     if (Phi.find(x) != Phi.end())
42.         return Phi[x];
43.     ll ans = vas(x);
44.     ll lst = 1;
45.     for (ll i = 2; i <= x; i++)
46.     {
47.         i = x / (x / i);
48.         ll w = (sqr(i) - sqr(lst)) % mod;
49.         ans = (ans - w * G(x / i) % mod) % mod;
50.         lst = i;
51.     }
52.     if (ans < 0)
53.         ans += mod;
54.     Phi.insert(make_pair(x, ans));
55.     return ans;
56. }
57. ll Ans(ll x)
58. {
59.     ll ans = 0, lst = 0;
60.     for (ll i = 1; i <= x; i++)
61.     {
62.         i = x / (x / i);
63.         ll z = seq(x / i);
64.         z = z * z % mod;
65.         ans = (ans + z * (G(i) - G(lst)) % mod) % mod;
66.         lst = i;
67.     }
68.     if (ans < 0)
69.         ans += mod;
70.     return ans;
71. }
72. int main()
73. {
74.     phi[1] = 1;
75.     for (int i = 2; i <= N - 5; i++)
76.     {
77.         if (!h[i])
78.         {
79.             phi[i] = i - 1;
80.             p[++cnt] = i;
81.         }
82.         for (int j = 1; j <= cnt; j++)
83.         {
84.             if (i * p[j] > N - 5)
85.                 break;
86.             h[i * p[j]] = 1;
87.             if (i % p[j] == 0)
88.                 phi[i * p[j]] = phi[i] * p[j];
89.             else
90.                 phi[i * p[j]] = phi[i] * (p[j] - 1);
91.         }
92.     }
93.     cin >> mod >> n;
94.     for (int i = 1; i <= N - 5; i++)
95.         g[i] = (g[i - 1] + 1ll * phi[i] * i % mod * i % mod) % mod;
96.     cout << Ans(n) << "\n";
97. }

复制代码

[/code]