laekov

优化方法暑假的时候zhx讲过，我居然还记得好感动。

Mobius反演加些奇异的东西。（不会用公式编辑器是不是已经落伍了）

两个优化-> sqrt(n)^2 == n。

跑得飞慢 。而且中间那坨又长又丑。

久了不写都快忘了。

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long qw;

#define _l (qw)

const int maxn = 10000009;

const int mod = 20101009;

int pn[maxn], mu[maxn], smu[maxn], tp;

bool pr[maxn];

void pre(int maxn) {

memset(pr, 0, sizeof(pr));

tp = 0;

mu[1] = 1;

for (int i = 2; i <= maxn; ++ i) {

if (!pr[i]) {

pn[tp ++] = i;

mu[i] = -1;

}

for (int j = 0; j < tp && i * pn[j] <= maxn; ++ j) {

pr[i * pn[j]] = 1;

if (i % pn[j])

mu[i * pn[j]] = -mu[i];

else {

mu[i * pn[j]] = 0;

break;

}

}

}

smu[0] = 0;

for (int i = 1; i <= maxn; ++ i)

smu[i] = (smu[i - 1] + _l mu[i] * i % mod * i % mod + mod) % mod;

}

int n, m, ans;

inline int segSum(int b, int e) {

return (((_l b + e) * (_l e - b + 1)) >> 1) % mod;

}

int calc(int m, int n) {

int ans = 0;

for (int i = 1, b; i <= n; i = b + 1) {

b = min(n / (n / i), m / (m / i));

ans = (_l ans + (_l smu[b] - smu[i - 1] + mod) * segSum(1, n / i) % mod * segSum(1, m / i) % mod % mod % mod) % mod;

}

return ans;

}

int main() {

#ifndef ONLINE_JUDGE

freopen("in.txt", "r", stdin);

#endif

scanf("%d%d", &n, &m);

if (n > m)

swap(n, m);

pre(n);

ans = 0;

for (int i = 1, b; i <= n; i = b + 1) {

b = min(n / (n / i), m / (m / i));

ans = (_l ans + _l segSum(i, b) * calc(m / i, n / i)) % mod;

}

printf("%d\n", ans);

}