一道莫名其妙的数学题
上次写博客不知道是什么时候了，我也不知道为什么突然想写博客
题面
若\(n=\prod p_i^{c_i}\)定义\(\tau(n)=\prod (-1)^{c_i},\xi(n)=\sum_{d|n}\tau(d)\)
我们需要得到\(\sum_{i=1}^n\sum_{j=1}^m \xi(ij)\)
\(n,m\leq 10^{12}\)
做法
先推式子，容易得到\(\tau(n)\)的狄拉克雷生成函数为\(\prod \frac{1}{1+{1\over p_i^x}}=\prod\frac{p_i^x}{p_i^x+1}\)
\(\xi=I*\tau=\prod (\frac{p_i^x}{p_i^x+1})(\frac{p_i^x}{p_i^x-1})=\prod\frac{p_i^{2x}}{p_i^{2x}-1}\)
所以\(\xi(n)=[\lfloor\sqrt n\rfloor^2=n]\)
设\(h(n)=\mu^2(n)\)
\[\sum_{i=1}^n\sum_{j=1}^m\xi(ij)\\
=\sum_{i=1}^n h(i)\left\lfloor\sqrt{\frac{n}{i}}\right\rfloor \left\lfloor\sqrt{\frac{m}{i}}\right\rfloor\\
\]
由于\(h\)在质数处的取值与\(I\)相同，所以我们考虑使用\(\mathbb{powerful\space number}\)筛法计算\(h(i)\)的前缀和
\[h=\prod(1+\frac{1}{p^z})\\
I=\prod\frac{p^z}{p^z-1}\\
u=h/I=\prod\frac{p^{2z}-1}{p^{2z}}=\prod(1-\frac{1}{p^{2z}})\\
\]
发现\(u(n)\)的值非常好求，为\(\xi(n)\mu(\sqrt n)\)，所以整除分块+\(\mathbb{powerful\space number}\)筛法计算\(h(i)\)的前缀和即可
下面计算时间复杂度：
\[T(n)=\sum_{i=1}^{n^{0.25}}(i+\frac{n^{0.5}}{i})\approx \sqrt n\ln n
\]
但是实际效率非常的高，可以在1s内跑过\(10^{14}\)
#include<bits/stdc++.h>
using namespace std;
# define ll long long
# define read read1<ll>()
# define Type template<typename T>
Type T read1(){
T t=0;
char k;
bool vis=0;
do (k=getchar())=='-'&&(vis=1);while('0'>k||k>'9');
while('0'<=k&&k<='9')t=(t<<3)+(t<<1)+(k^'0'),k=getchar();
return vis?-t:t;
}
# define fre(k) freopen(k".in","r",stdin);freopen(k".out","w",stdout)
int tot,prime[1000005];
ll n,m;
bool vis[1000005];
void init(const int N=1000000){
for(int i=2;i<=N;++i){
if(!vis[i])prime[++*prime]=i;
for(int j=1;j<=*prime&&prime[j]*i<=N;++j){
vis[i*prime[j]]=1;
if(!(i%prime[j]))break;
}
}
}
ll Getv(ll s,int w,int p){
ll t=s*p;
if(w>*prime)return t;
while(w<=*prime&&1ll*prime[w]*prime[w]<=s){
ll j=1ll*prime[w]*prime[w];
t+=Getv(s/j,w+1,-p);
++w;
}return t;
}ll Sqrt(ll x){
ll v=sqrt(x);
while(v*v<x)++v;
while(v*v>x)--v;
return v;
}
ll Getr(ll v){
ll t=Sqrt(n/v);
ll o=t?n/t/t:n;
t=Sqrt(m/v);
o=min(o,t?m/t/t:m);
return o;
}
int main(){init();
fre("lost");
n=read,m=read;
if(n>m)swap(n,m);
ll ans=0,la=0;
for(ll l=1,r=0,nw=0;l<=n;l=r+1){
r=Getr(l);nw=Getv(r,1,1);
ans+=(nw-la)*Sqrt(n/l)*Sqrt(m/l);
la=nw;
}cout<<ans;
return 0;
}
第一次写\(\mathbb{powerful number}\)筛，居然没出锅！