洛谷p1829(莫比乌斯反演)

思路：

?代码：

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const double eps = 1e-8;
const int N = 1e7+10;
const long long ?mod = 20101009;
#define LL long long?
int pre[N],st[N];
int n,cn,m;
LL mu[N];
LL g(int l, int k)
{
? ? return (LL)k / (k / l);
}
void into()
{
? ? mu[1] = 1;
? ? for (int i = 2; i <= N; i++)
? ? {
? ? ? ? if (!st[i]) pre[++cn] = i, mu[i] = -1;
? ? ? ? for (int j = 1; pre[j] * i <= N&&j<=cn; j++)
? ? ? ? {
? ? ? ? ? ? st[pre[j] * i] = 1;
? ? ? ? ? ? if (i % pre[j] == 0) break;
? ? ? ? ? ? mu[i*pre[j]] = -mu[i];
? ? ? ? }
? ? }
? ? for (int i = 1; i <= N; i++)
? ? ? ? mu[i] = ((LL)mu[i]*i%mod*i%mod+mu[i - 1])%mod;
}
LL gd(int l, int r)
{
? ? return (LL)(r - l + 1) * (r + l) / 2%mod;
}
LL f(int n, int m)
{
? ? LL res = 0;
? ? for (int r,l = 1; l <= n; l = r + 1)
? ? {
? ? ? ? r = ?min(n,(int)min(g(l, n), g(l, m)));
? ? ? ? res = (res + (LL)(mu[r] - mu[l - 1]) * gd(1,n/l) % mod *gd(1,m/l)% mod) % mod;
? ? }
? ? return res;
}
int main()
{
? ? into();
? ? cin >> n >> m;
? ? if (n >m)swap(n, m);
? ? LL ans = 0;
? ? for (int r,l = 1; l <= n; l = r + 1)
? ? {
? ? ? ? r = ?min(n,(int)min(g(l, n), g(l, m)));
? ? ? ? ans = (ans + (LL)gd(l,r)% mod * (LL)f(n / l, m / l) % mod) % mod;
? ?}
? ? cout << (ans % mod + mod) % mod << endl;
? ? return 0;
}