洛谷P3768 简单的数学题 题解
题目链接:P3768 简单的数学题
题意:
输入一个整数 \(n\) 和一个整数 \(p\),你需要求出:
\[ \left(\sum_{i=1}^n\sum_{j=1}^n ij \gcd(i,j)\right) \bmod p \] 其中 \(\gcd(a,b)\) 表示 \(a\) 与 \(b\) 的最大公约数。
输入格式:
一行两个整数 \(p,n\)。
输出格式:
一行一个整数表示答案。
数据范围:
\(1\le n \le 10^{10},~5 \times 10^8 \leq p \leq 1.1 \times 10^9\) 且 \(p\) 为质数。时限 4s。
考虑欧拉反演。 \[ \begin{aligned} \sum_{i=1}^n \sum_{j=1}^n i j \operatorname{gcd}(i, j) & =\sum_{i=1}^n \sum_{j=1}^n i j \sum_{k\mid i,\, k\mid j} \varphi(k) \\[4pt]& =\sum_{k=1}^n \varphi(k) \sum_{k \mid i} \sum_{k \mid j} i j \\[4pt]& =\sum_{k=1}^n \varphi(k) \cdot k^2 \cdot \left(\sum_{i=1}^{\left\lfloor n/k \right\rfloor} i\right)^2 \\[4pt]& =\sum_{k=1}^n k^2\varphi(k) \sum_{i=1}^{\left\lfloor n/k\right\rfloor} i^3 \\[4pt]& =\sum_{k=1}^n k^2\varphi(k) S\left(\left\lfloor n/k\right\rfloor\right) && S(n) = \left(\frac{n(n+1)}{2}\right)^2 \end{aligned} \] 显然 \(S(n)\) 可以数论分块,因此我们只需要求出 \(k^2\varphi(k)\) 的前缀和。
考虑杜教筛。记 \(f=\varphi \cdot \mathrm{id}^2\) ,设 \(g=\mathrm{id}^2\) ,则 \[ \begin{aligned} (f*g)(n) &= \sum_{d \mid n}\varphi(d)d^2\cdot \frac{n^2}{d^2} \\[6pt] &= n^2\sum_{d \mid n}\varphi(d) \\[6pt] &= n^3 \end{aligned} \] 那么前缀和就是一个 \(\sum i^2\) 和 \(\sum i^3\) ,分别是 \(\frac{n(n+1)(2 n+1)}{6}\) 和 \(\left(\frac{n(n+1)}{2}\right)^2\) 。
时间复杂度 \(\mathcal{O}(n^{\frac{2}{3}})\) ,因为杜教筛有记忆化,所以筛一次就能筛出这 \(\mathcal{O}(\sqrt{n})\) 个值。
代码:
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(5e6 + 15))
char ck[N]; int inv, pcnt, mod, p[N], phi[N], sum_phi[N];
unordered_map<int, int> vis;
void add(int &x, int y) { (x += y) >= mod ? x -= mod : 0; }
int qpow(int a, int b)
{
int r = 1;
for(a %= mod; b > 0; b >>= 1, a = a * a % mod)
if(b & 1) r = r * a % mod;
return r;
}
void init(const int _ = N - 5)
{
phi[1] = 1;
rep(i, 2, _)
{
if(!ck[i]) { p[++pcnt] = i; phi[i] = i - 1; }
for(int j = 1; j <= pcnt && i * p[j] <= _; j++)
{
const int pos = i * p[j]; ck[pos] = true;
if(i % p[j]) { phi[pos] = phi[i] * phi[p[j]]; }
else { phi[pos] = phi[i] * p[j]; break; }
}
}
rep(i, 1, _) add(sum_phi[i], (sum_phi[i - 1] + i * i % mod * phi[i] % mod) % mod);
}
int fun2(int x) { x %= mod; return x * (x + 1) % mod * (2 * x % mod + 1) % mod * inv % mod; }
int fun3(int x) { x %= mod; const int y = (x * (x + 1) / 2) % mod; return y * y % mod; }
int getsum(int n)
{
if(n <= N - 5) return sum_phi[n];
if(vis[n]) return vis[n];
int res = fun3(n);
for(int l = 2, r; l <= n; l = r + 1)
{
r = n / (n / l);
add(res, mod - (fun2(r) - fun2(l - 1) + mod) % mod * getsum(n / l) % mod);
}
return vis[n] = res;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
int n; cin >> mod >> n; init();
int res = 0; inv = qpow(6ll, mod - 2);
for(int l = 1, r; l <= n; l = r + 1)
{
r = n / (n / l);
add(res, (getsum(r) - getsum(l - 1) + mod) % mod * fun3(n / l) % mod);
}
cout << res << '\n';
return 0;
}
参考文献: