摘要:莫反后数论分块

[国家集训队]Crash的数字表格 / JZPTAB

题面

题目分析

设$n\leq m$.

设$sum(n,m)=\sum_{i=1}^{n}\sum_{j=1}^{m} \varepsilon(~gcd(i,j)~)\cdot i\cdot j$,根据$\mu*1=\varepsilon$进行反演:

设$i=i’ \cdot d$,$j=j’ \cdot d$:

发现可以用数论分块求,现在将$sum(n,m)$回代:

这又可以通过数论分块来求.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include "iostream"
#include "cstdlib"
#include "cstdio"
#include "cstring"
#include "cmath"
#include "cctype"
#include "ctime"
#include "iomanip"
#include "algorithm"
#include "set"
#include "queue"
#include "map"
#include "stack"
#include "deque"
#include "vector"
#define R register
#define INF 0x3f3f3f3f
#define debug(x) printf("debug:%lld\n",x)
#define debugi(x) printf("debug:%d\n",x)
#define debugf(x) printf("debug:%llf\n",x)
#define endl putchar('\n')
typedef long long lxl;
const lxl big=10000010,mod=20101009;
lxl n,m,PrimeCnt,ans;
lxl mu[big],pri[big],PreMu[big],vis[big];
inline lxl read()
{
char c(getchar());
lxl f(1),x(0);
for(;!isdigit(c);(c=='-')&&(f=-1),c=getchar());
for(;isdigit(c);x=(x<<1)+(x<<3)+(c^48),c=getchar());
return f*x;
}
inline void prework()
{
mu[1]=1;
for(R int i(2);i<big;++i)
{
if(!vis[i])pri[++PrimeCnt]=i,vis[i]=true,mu[i]=-1;
for(R int j(1);j<=PrimeCnt;++j)
{
if(pri[j]*i>big)break;
vis[pri[j]*i]=true;
if(!(i%pri[j])){mu[i*pri[j]]=0;break;}
mu[i*pri[j]]=-mu[i];
}
}
}
inline lxl sum(lxl a,lxl b)
{
return ((a*(a+1))/2%mod*(b*(b+1))/2%mod)%mod;
}
inline lxl func(lxl x ,lxl y)
{
lxl res(0);
for(R int i(1),j;i<=std::min(x,y);i=j+1)
{
j=std::min(x/(x/i),y/(y/i));
res=(res+(PreMu[j]-PreMu[i-1]+mod)%mod*sum(x/i,y/i)%mod)%mod;
}
return res;
}
int main(void)
{
prework();
n=read(),m=read();
for(R int d(1);d<=n;++d)PreMu[d]=(PreMu[d-1]+(mu[d]+mod)*(d*d)%mod)%mod;
for(R int i(1),j;i<=std::min(n,m);i=j+1)
{
j=std::min(n/(n/i),m/(m/i));
ans=(ans+(j-i+1)*(i+j)/2%mod*func(n/i,m/i)%mod)%mod;
}
printf("%lld\n",ans-1);
return 0;
}