莫比乌斯
YY的GCD
\[\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)\in prime] \]\(\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;=\sum_{p\in prime}\sum_{i=1}^{\left\lfloor\dfrac{n}{p}\right\rfloor}\sum_{j=1}^{\left\lfloor\dfrac{m}{p}\right\rfloor}\sum_{d|gcd(i,j)}{\mu(d)}\)
\(\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;=\sum_{p\in prime}\sum_{d=1}^{min(n/p,m/p)}\mu(d)\:*\:{\left\lfloor\dfrac{n}{pd}\right\rfloor}\:*\:{\left\lfloor\dfrac{m}{pd}\right\rfloor}\)
\(\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;=\sum_{k=1}^{n}f(k)\:*\:{\left\lfloor\dfrac{n}{k}\right\rfloor}\:*\:{\left\lfloor\dfrac{m}{k}\right\rfloor}\)
\[f(x) = \sum_{p\in prime} \mu(\frac{x}{p}) \]\[f(x) = \begin{cases}\mu(1)&x=1\\ \mu(i)&i \mod y= 0\\ -f(i) + \mu(i)& i \mod y \neq 0\end{cases} \]数论分块 + 前缀和
#include
#define Starseven main
#define ll long long
namespace lyt {
void read(int &x){
char ch=getchar();int re=0,op=1;
while(ch<'0'||ch>'9'){if(ch=='-') op=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){re=(re<<3)+(re<<1)+ch-'0';ch=getchar();}
x = re * op;
return ;
}
void read(long long &x){
char ch=getchar();long long re=0,op=1;
while(ch<'0'||ch>'9'){if(ch=='-') op=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){re=(re<<3ll)+(re<<1ll)+ch-'0';ch=getchar();}
x = re * op;
return ;
}
void write(int x){
if(x<0){putchar('-');x=-x;}
if(x>9) write(x/10);
putchar(x%10+'0');
return ;
}//记得自己加空格和换行
void write(long long x){
if(x<0){putchar('-');x=-x;}
if(x>9) write(x/10);
putchar(x%10+'0');
return ;
}//记得自己加空格和换行
int max(int x,int y){return x m) n ^= m ^= n ^= m;
ll ans = 0;
for (int i = 1, j; i <= n; i = j + 1) {
j = min(n / (n / i), m / (m / i));
ans += 1ll * (f[j] - f[i - 1]) * (n / i) * (m / i);
}
write(ans);puts("");
}
return 0;
}
约数个数和
闲话：
为什么大家做题是越做越熟练，我是越做越茫然？
\[\begin{aligned} \sum_{i=1}^{n}\sum_{j=1}^{m}d(ij) & = \sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{x|i}\sum_{y|j}[gcd(x,y)=1] \\ & = \sum_{x=1}^{n}\sum_{y=1}^{m}\:*\:{\left\lfloor\dfrac{n}{x}\right\rfloor}\:*\:{\left\lfloor\dfrac{m}{y}\right\rfloor}[gcd(x,y)=1] \\ & = \sum_{x=1}^{n}\sum_{y=1}^{m}{\left\lfloor\dfrac{n}{x}\right\rfloor}\:*\:{\left\lfloor\dfrac{m}{y}\right\rfloor}\:*\:\sum_{t|gcd(x,y)}\mu(t) \\ & = \sum_{t=1}^{min(n,m)}\mu(t)\times \sum_{x=1}^{\left\lfloor\dfrac{n}{t}\right\rfloor}\sum_{y=1}^{\left\lfloor\dfrac{m}{t}\right\rfloor}\left\lfloor\dfrac{n}{xt}\right\rfloor\:*\:\left\lfloor\dfrac{m}{xt}\right\rfloor \\ & = \sum_{t=1}^{min(n,m)}\mu(t)\times \sum_{x=1}^{\left\lfloor\dfrac{n}{t}\right\rfloor}\left\lfloor\dfrac{\left\lfloor\dfrac{n}{x}\right\rfloor}{t}\right\rfloor\times \sum_{x=1}^{\left\lfloor\dfrac{m}{t}\right\rfloor}\left\lfloor\dfrac{\left\lfloor\dfrac{m}{x}\right\rfloor}{t}\right\rfloor \end{aligned} \]\[\text{莫比乌斯反演的“套路”} \text{设}f(x) = \sum_{i=1}^{x}{\left\lfloor\dfrac{x}{i}\right\rfloor} \]\[ans=\sum_{t=1}^{min(n,m)}\mu(t)\times f(\left\lfloor\dfrac{n}{t}\right\rfloor)\times f(\left\lfloor\dfrac{m}{t}\right\rfloor) \]\(\mu\)用前缀和
而f函数可以用数论分块\(O(\sqrt{N})\)
#include
#include
#include
#include
using namespace std;
const int maxn=50000+5;
int n,m,cas,cnt,mu[maxn],pri[maxn],vis[maxn];
long long ans,f[maxn];
inline long long calc(int x){
long long res=0;
for(int i=1,r;i<=x;i=r+1){
r=x/(x/i);
res+=(x/i)*(r-i+1);
}
return res;
}
inline void prework(void){
mu[1]=1;
for(int i=2;i<=50000;i++){
if(!vis[i])
vis[i]=1,pri[++cnt]=i,mu[i]=-1;
for(int j=1;j<=cnt&&i*pri[j]<=50000;j++){
vis[i*pri[j]]=1;
if(i%pri[j]==0){
mu[i*pri[j]]=0;break;
}
mu[i*pri[j]]=-mu[i];
}
}
for(int i=1;i<=50000;i++) mu[i]+=mu[i-1],f[i]=calc(i);
}
signed main(void){
scanf("%d",&cas);prework();
while(cas--){
scanf("%d%d",&n,&m);
if(n>m) swap(n,m);ans=0;
for(int i=1,r;i<=n;i=r+1){
r=min(n/(n/i),m/(m/i));
ans+=f[n/i]*f[m/i]*(mu[r]-mu[i-1]);
}
printf("%lld\n",ans);
}
return 0;
}
（我裂开来）
Crash的数字表格
\[ans=\sum_{i=1}^{n}\sum_{j=1}^{m}lcm(i,j) \]\[\begin{aligned} \sum_{i=1}^{n}\sum_{j=1}^{m}lcm(i,j) & = \sum_{t=1}^{min(n,m)}t\times \sum_{i=1}^{\left\lfloor\dfrac{n}{t}\right\rfloor}\sum_{j=1}^{\left\lfloor\dfrac{m}{t}\right\rfloor}(i\times j)[gcd(i,j=1)] \\ & = \sum_{t=1}^{min(n,m)}t\times \sum_{i=1}^{\left\lfloor\dfrac{n}{t}\right\rfloor}\sum_{j=1}^{\left\lfloor\dfrac{m}{t}\right\rfloor}i\times j\times(\sum_{h|gcd(i,j)}\mu(h)) \\ & = \sum_{t=1}^{min(n,m)}t\times\sum_{h=1}^{min(\left\lfloor\dfrac{m}{t}\right\rfloor,\left\lfloor\dfrac{n}{t}\right\rfloor)}\mu(h)\times h^2 \times\sum_{x=1}^{\left\lfloor\dfrac{n}{th}\right\rfloor}x \times \sum_{y=1}^{\left\lfloor\dfrac{m}{th}\right\rfloor}y \end{aligned} \]然后我们观察式子
\[ans=\sum_{t=1}^{min(n,m)}t\times\sum_{h=1}^{min(\left\lfloor\dfrac{m}{t}\right\rfloor,\left\lfloor\dfrac{n}{t}\right\rfloor)}\mu(h)\times h^2 \times\sum_{x=1}^{\left\lfloor\dfrac{n}{th}\right\rfloor}x \times \sum_{y=1}^{\left\lfloor\dfrac{m}{th}\right\rfloor}y \]我们就可以设
\[behind(x,y)=\sum_{h=1}^{min(x,y)}\mu(h)\times h^2 \times \sum_{i=1}^{\left\lfloor\dfrac{x}{h}\right\rfloor}i \times \sum_{j=1}^{\left\lfloor\dfrac{y}{h}\right\rfloor}j \]这个式子是不是可以预处理一下？
就是三个前缀和拼凑！
然后数论分块可以求出\(behind(x,y)\)的值！
\[ans=\sum_{t=1}^{min(n,m)}t\times behind(\left\lfloor\dfrac{n}{t}\right\rfloor,\left\lfloor\dfrac{m}{t}\right\rfloor) \]又是一个数论分块！
所以就解决了
#include
#define Starseven main
#define ll long long
namespace lyt {
void read(int &x){
char ch=getchar();int re=0,op=1;
while(ch<'0'||ch>'9'){if(ch=='-') op=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){re=(re<<3)+(re<<1)+ch-'0';ch=getchar();}
x = re * op;
return ;
}
void read(long long &x){
char ch=getchar();long long re=0,op=1;
while(ch<'0'||ch>'9'){if(ch=='-') op=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){re=(re<<3ll)+(re<<1ll)+ch-'0';ch=getchar();}
x = re * op;
return ;
}
void write(int x){
if(x<0){putchar('-');x=-x;}
if(x>9) write(x/10);
putchar(x%10+'0');
return ;
}//记得自己加空格和换行
void write(long long x){
if(x<0){putchar('-');x=-x;}
if(x>9) write(x/10);
putchar(x%10+'0');
return ;
}//记得自己加空格和换行
int max(int x,int y){return x mod) mu[i] %= mod;
add[i] = add[i - 1] + i;
if(add[i] > mod) add[i] %= mod;
}
return ;
}
ll Behind(ll x, ll y) {
ll re = 0;
for (ll h = 1; h <= min(x, y); h++) {
ll g = min(x / (x / h), y / (y / h));
ll a = x / h, b = y / h;
re += (mu[g] - mu[h - 1]) % mod * add[a] % mod * add[b] % mod;
if(re > mod) re %= mod;
h = g;
}
re += mod;
return (re % mod);
}
int Starseven(void) {
ll n, m;
read(n);
read(m);
if(n > m) swap(n, m);
Init();
ll ans = 0;
for (ll t = 1; t <= n; t++) {
ll x = min(n / (n / t), m / (m / t));
ll behind = Behind(n / t, m / t);
ans = (ans + (x - t + 1) * (x + t) / 2 * behind) % mod;
t = x;
}
write(ans);puts("");
return 0;
}
数表
\[ans=\sum_{i=1}^{n}\sum_{j=1}^{m}[a\geq\sum_{d|gcd(i,j)}d]\times\sum_{d|gcd(i,j)}d \]我们假设
\[G(n,m)=\sum_{d|gcd(n,m)}d \]\[n \leq m \] \[\begin{aligned} G(n,m) & = \sum_{d|gcd(n,m)}d \\ & = \sum_{d=1}^{n}d\times[d|gcd(n,m)] \\ & = \sum_{d=1}^nd\times[mn=\left\lfloor\dfrac{nm}{d^2}\right\rfloor\times d^2] \end{aligned} \]这个思路有点难走，那我们换个思路
\[ans=(\sum_{i=1}^n\sum_{j=1}^m\sum_{d|gcd(i,j)}d)-(\sum_{i=1}^n\sum_{j=1}^m[a<\sum_{d|gcd(i,j)}d]\times\sum_{d|gcd(i,j)}d) \]我们设前面的式子为sum(n,m),则
\[\begin{aligned} sum(n,m) & =\sum_{i=1}^n\sum_{j=1}^m\sum_{d|gcd(i,j)}d \\ & =\sum_{d=1}^nd\times \left\lfloor\dfrac{n}{d}\right\rfloor\times\left\lfloor\dfrac{m}{d}\right\rfloor \end{aligned} \]这个可以用数论分块
然后我们发现其实后面的式子和上面没有用减法原理的式子一样，所以失败
这个时候，我们发现我们最开始枚举的东西就是除数函数！
（其实我没有发现，是看题解才知道的）
所以我们可以写出sum(n,m)的另一个版本
\[\begin{aligned} sum(n,m) & = \sum_{i=1}^n\sum_{j=1}^m\sigma(gcd(i,j)) \\ & = \sum_{t=1}^{n}\sigma(t)\sum_{i=1}^{\left\lfloor\dfrac{n}{t}\right\rfloor}\sum_{j=1}^{\left\lfloor\dfrac{m}{t}\right\rfloor}[gcd(i,j)=1] \\ & = \sum_{t=1}^{n}\sigma(t)\sum_{i=1}^{\left\lfloor\dfrac{n}{t}\right\rfloor}\sum_{j=1}^{\left\lfloor\dfrac{m}{t}\right\rfloor}\sum_{d|gcd(i,j)}\mu(d) \\ & = \sum_{t=1}^{n}\sigma(t)\sum_{d=1}^{\left\lfloor\dfrac{n}{t}\right\rfloor}\mu(d)\left\lfloor\dfrac{n}{dt}\right\rfloor\left\lfloor\dfrac{m}{dt}\right\rfloor \\ & =\sum_{T=1}^{n}\left\lfloor\dfrac{n}{T}\right\rfloor\left\lfloor\dfrac{m}{T}\right\rfloor\sum_{d|T}\sigma(d)\mu(\frac{T}{d}) \end{aligned} \]此时，前面的求和可以分块\(O(n + m)\),后面的是个积性函数，可以预处理，然后就是O(1)
但是，不是每个东西都对答案有贡献，所以我们要排除掉没有贡献的.
然后就需要维护答案，想到维护这个词，在看一下式子，
\[\color{red}\text{单点修改，区间查询} \]这不就是树状数组吗？
所以我鸽了……
P4450 双亲数
题解
P4449 于神之怒加强版
题解
P3911 最小公倍数之和
题解
P6156 简单题
题解
P1891 疯狂 LCM
题解