P1390公约数的和
简单莫反题。要求
可以先考虑问题的简化版：
然后用一个数论分块，就可以求出该柿子。
再考虑题目中要求我们算的柿子，设它为\(ans\)。
不难发现\(\sum_{i=1}^{n}\sum_{j=1}^ngcd(i,j)=ans\times 2+\sum_{i=1}^{n}gcd(i,i)=ans\times 2+\frac{n\times (n+1)}{2}\)
然后就能愉快地求出来了。
P1447能量采集
不难发现，题目让我们求的是\(\sum_{i=1}^{n}\sum_{j=1}^{m}2\times gcd(i,j)-n\times m\)
于是就转化成为了上一题。\(ans=2\times \sum_{d=1}^nd\sum_{i=1}^{\lfloor \frac{n}{d}\rfloor}\mu(i)\lfloor \frac{n}{di}\rfloor\lfloor \frac{m}{di}\rfloor -n\times m\)（这里假定\(n>=m\)）
YY的GCD
莫反\(+\)一个小优化。先假定\(n>=m\)。仍是按照第一题的方式推柿子，\(ans=\sum_{d=1}^n\sum_{i=1}^{\lfloor \frac{n}{d}\rfloor}\mu(i)\lfloor \frac{n}{di}\rfloor\lfloor \frac{m}{di}\rfloor(d\in prime)\)
然而这样复杂度是\(O(n\space logn)\)的，仍会超时，肿么办？
注意到，数对 \((i,d)\) 相当于枚举了所有乘积小于等于 \(n\) 的数（且后一个数是质数）。令 \(T=i\times d\)，考虑枚举每一个 \(T\) 对答案有多少贡献（这是一个套路，后面会经常用）：
然后发现， \(\sum_{k|T,k\in prime}^{} \mu( \frac{T}{k})\) 是可以预处理的。枚举每一个质数 \(p\) ，然后令它的倍数 \(k\) 加上 \(\mu(\frac{k}{p})\) 。
\(code:\)
void work(){
ll r=0,a=n,b=m;
if(a<b) swap(a,b);
for(int i=1;i<=b;i=r+1){
r=min(a/(a/i),b/(b/i));
if(r>b) r=b;
ans+=(sum[r]-sum[i-1])*(a/i)*(b/i);//注意是a/i下取整，要加括号
}
}
int main(){
for(int i=1;i<=maxn;++i)
miu[i]=1;
for(int i=2;i<=maxn;++i){
if(!vis[i]){
p[++tot]=i,miu[i]=-1;
for(int j=i*2;j<=maxn;j+=i){
vis[j]=1;
if(j/i%i==0) miu[j]=0;
else miu[j]*=-1;
}
}
}
for(int i=1;i<=maxn;++i)
for(int j=1;p[j]*i<=maxn&&j<=tot;++j)
s[i*p[j]]+=miu[i];
for(int i=1;i<=maxn;++i)
sum[i]=sum[i-1]+s[i];
scanf("%lld",&t);
while(t--){
scanf("%lld%lld",&n,&m);
ans=0;
work();
printf("%lld\n",ans);
}
return 0;
}
P3327约数个数和
前言：一些常用的二级结论：
推柿子参看题解区
然后令\(F(n)=\sum_{i=1}^n\lfloor\frac{n}{i}\rfloor\)，则
然后用数论分块即可。时间复杂度 \(O(n\space \sqrt n+T\space \sqrt n)\) 。
\(code;\)
void work(){
scanf("%lld%lld",&n,&m);
if(n<m)
swap(n,m);
int ans=0;
for(int i=1,r=0,rr=0;i<=m;i=r+1){
r=n/(n/i);rr=m/(m/i);//cout<<r<<" "<<rr<<endl;
r=min(r,min(rr,m));//cout<<m/i<<" "<<m/r<<" "<<n/i<<" "<<n/r<<endl;
ans+=(miu[r]-miu[i-1])*s[m/i]*s[n/i];
}
printf("%lld\n",ans);
}
signed main(){
scanf("%lld",&t);
for(int i=2;i<=100000;++i){
if(a[i]==0)
p[++tot]=i,a[i]=i;
for(int j=1;j<=tot;++j){
if(i*p[j]>100000||a[i]<p[j])
break;
a[i*p[j]]=p[j];
}
}
for(int i=1;i<=100000;++i)
miu[i]=1;
for(int i=2;i<=100000;++i){
int tmp=i/a[i];
if(tmp%a[i]==0)
miu[i]=0;
else
miu[i]=-miu[tmp];
}
for(int i=1;i<=100000;++i)
miu[i]+=miu[i-1];
for(int i=1;i<=100000;++i){
for(int j=1,r=0;j<=i;j=r+1){
r=i/(i/j);
s[i]+=(r-j+1)*(i/j);
}
}
while(t--)
work();
//for(int i=1;i<=100;++i)cout<<miu[i]<<" ";cout<<endl;
return 0;
}
P3768简单的数学题
利用 \(\phi*1=id\) 可以得到：
其中 \(F(n)=n\times (n+1)/2\)
其中 \(\sum_{d=1}^{n}F^2(\lfloor \frac{n}{d}\rfloor)\) 可以用数论分块处理，剩下的部分考虑杜教筛。
剩下的部分是 \(d^2\phi(d)\) ，设 \(\sum_{d=1}^{n}d^2\phi(d)\) 为 \(s(n)\) ，考虑构造函数 \(g(n)=n^2\) ，则有：
化简得到：
P3312数表
先不考虑 \(a\) 的限制，有：
(其中 \(f(x)\) 表示 \(x\) 的因数和，可以预处理得到)
接下来考虑 \(a\) 。首先将询问按照 \(a\) 从小到大排序，然后开一个树状数组（其中单点\(i\)表示 \((f*\mu)(i)\) ），每次遇到可以加入树状数组的 \(f(i)\) ，就枚举 \(i\) 的倍数，令 \(ki\) 的单点数值增加 \(f(i)\times\mu(k)\) 。然后在数论分块的时候，如果当前区间为 \([l,r]\) ，就让 \(ans\) 乘以 \([l,r]\) 的区间和。
\(code:\)
bool cmp(node a,node b){
return a.a<b.a;
}
bool cmp2(node a,node b){
return a.w<b.w;
}
void add(long long x,long long w){
while(x<=L)
c[x]=(c[x]+w)%mod,x+=x&(-x);
}
long long ask(long long x){
long long re=0;
while(x)
re=(re+c[x])%mod,x-=x&(-x);
return re;
}
long long work(long long n,long long m){
int ans=0;
if(n<m)
swap(n,m);
for(int i=1,r=0;i<=m;i=r+1){
r=min(n/(n/i),min(m/(m/i),m));
ans=(ans+((n/i)%mod*(m/i)%mod*((ask(r)-ask(i-1)+mod)%mod)%mod))%mod;
}
return ans;
}
void pre_work(){
for(int i=2;i<=L;++i){
if(a[i]==0)
a[i]=i,prime[++tot]=i;
for(int j=1;j<=tot;++j){
if(prime[j]*i>L||prime[j]>a[i])
break;
a[i*prime[j]]=prime[j];
}
}
miu[1]=1;
for(int i=2;i<=L;++i){
int j=i/a[i];
if(j%a[i]==0)
miu[i]=0;
else
miu[i]=miu[j]*(-1);
}
for(int i=1;i<=tot;++i){
long long now=prime[i];
p[now][0]=sum[now][0]=1;
long long tmp=0;
while(sum[now][tmp]<=L){
++tmp;
p[now][tmp]=p[now][tmp-1]*prime[i];
sum[now][tmp]=(sum[now][tmp-1]+p[now][tmp]);
}
}
for(int i=1;i<=L;++i){
long long tmp=i,cnt=0;
f[i].w=1;f[i].id=i;
for(int j=1;j<=tot&&prime[j]*prime[j]<=i;++j){
cnt=0;
while(tmp%prime[j]==0)
tmp/=prime[j],++cnt;
f[i].w=f[i].w*sum[prime[j]][cnt];
}
if(tmp!=1)
f[i].w=f[i].w*sum[tmp][1];
}
sort(f+1,f+L+1,cmp2);
}
signed main(){
pre_work();
scanf("%lld",&t);
for(int i=1;i<=t;++i)
scanf("%lld%lld%lld",&v[i].n,&v[i].m,&v[i].a),v[i].id=i;
sort(v+1,v+t+1,cmp);
for(int i=1,j=1;i<=t;++i){
while(j<=L&&f[j].w<=v[i].a){
for(int k=f[j].id;k<=L;k+=f[j].id)
add(k,f[j].w*miu[k/f[j].id]%mod);
++j;
}
ans[v[i].id]=work(v[i].n,v[i].m);
}
for(int i=1;i<=t;++i)
printf("%lld\n",ans[i]);
return 0;
}