图片看不了,猜一手ub,你可以贴一下code
by N_z_ @ 2021-12-06 17:15:24
Code
```c
#include <bits/stdc++.h>
using namespace std;
#define int long long
namespace IO {
template <typename T>
inline void read(T &x) {
x = 0; int r = 1;
char ch = getchar();
while (!isdigit(ch)) r = ch == '-' ? -1 : 1, ch = getchar();
while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
x *= r;
}
template <typename T>
inline void write(T x) {
if (x < 0) putchar('-'), x = -x;
if (x > 9) write(x / 10);
putchar(x % 10 + '0');
}
}
const int N = 4e6 + 5;
using namespace IO;
int inv4, inv6;
int n, mod;
int phi[N], pri[N], sum[N], cnt;
bool isp[N];
map<int, int> f_sum;
int add(int x) {
return x < mod ? x : x - mod;
}
int sub(int x) {
return x < 0 ? x + mod : x;
}
int qpow(int a, int b) {
int res = 1;
while (b) {
if (b & 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
int s2(int x) {
return x * (x + 1) % mod * (2 * x + 1) % mod * inv6 % mod;
}
int s3(int x) {
return (x * (x + 1) / 2 % mod) * (x * (x + 1) / 2 % mod) % mod;
}
void Init(int n) {
phi[1] = 1;
inv4 = qpow(4, mod - 2);
inv6 = qpow(6, mod - 2);
for (int i = 2; i < n; ++ i) {
if (!isp[i]) {
pri[++ cnt] = i;
phi[i] = i - 1;
}
for (int j = 1; j <= cnt; ++ j) {
if (pri[j] * i > n) break;
isp[i * pri[j]] = true;
if (i % pri[j] == 0) {
phi[i * pri[j]] = phi[i] * pri[j];
break;
}
phi[i * pri[j]] = phi[i] * phi[pri[j]];
}
}
for (int i = 1; i <= n; ++ i) {
sum[i] = add(sum[i - 1] + 1ll * i * i % mod * phi[i] % mod);
}
}
int Sum_phi(int n) {
if (n < N) return sum[n];
if (f_sum.count(n)) return f_sum[n];
int res = s3(n);
for (int l = 2, r; l <= n; l = r + 1) {
r = min(n, n / (n / l));
res = sub(res - sub(s2(r) - s2(l - 1)) * Sum_phi(n / l) % mod);
}
return f_sum[n] = res;
}
void solve(int n) {
int res = 0;
for (int l = 1, r; l <= n; l = r + 1) {
r = min(n, n / (n / l));
res = add(res + sub(Sum_phi(r) - Sum_phi(l - 1)) * s3(n / l) % mod);
}
write(res);
}
signed main() {
// freopen("P3768_1.in", "r", stdin);
// freopen("P3768_1.ans", "w", stdout);
read(mod), read(n);
Init(N);
solve(n);
}
```
by ShuKuang @ 2021-12-06 17:17:25
@[N_z_](/user/320087)
感谢提醒。
欧筛范围的ub。
已过。
by ShuKuang @ 2021-12-06 17:22:54