数论函数

标签：lfloor frac 函数数论 sum rfloor mu gcd

P1390公约数的和

简单莫反题。要求

\[\sum_{i=1}^{n}\sum_{j=i+1}^ngcd(i,j) \]

可以先考虑问题的简化版：

\[\sum_{i=1}^{n}\sum_{j=1}^ngcd(i,j) \]

\[=\sum_{d=1}^nd\sum_{i=1}^{n}\sum_{j=1}^n[gcd(i,j)==d] \]

\[=\sum_{d=1}^nd\sum_{i=1}^{\lfloor \frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor \frac{n}{d}\rfloor}[gcd(i,j)==1] \]

\[=\sum_{d=1}^nd\sum_{i=1}^{\lfloor \frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor \frac{n}{d}\rfloor}\sum_{k|gcd(i,j)}^{gcd(i,j)} \mu(k) \]

\[=\sum_{d=1}^nd\sum_{i=1}^{\lfloor \frac{n}{d}\rfloor}\mu(i)\sum_{i|j}^{\lfloor \frac{n}{d}\rfloor} \sum_{i|k}^{\lfloor \frac{n}{d}\rfloor}1 \]

\[=\sum_{d=1}^nd\sum_{i=1}^{\lfloor \frac{n}{d}\rfloor}\mu(i)\lfloor \frac{n}{di}\rfloor^2 \]

然后用一个数论分块，就可以求出该柿子。

再考虑题目中要求我们算的柿子，设它为\(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\) 对答案有多少贡献（这是一个套路，后面会经常用）：

\[ans=\sum_{T=1}^n\lfloor \frac{n}{T}\rfloor\lfloor \frac{m}{T}\rfloor\sum_{k|T,k\in prime}^{} \mu( \frac{T}{k}) \]

然后发现， \(\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约数个数和

前言：一些常用的二级结论：

\[\mu(ij)=\mu(i)\mu(j)[gcd(i,j)==1] \]

\[d(ij)=\sum_{x|i}\sum_{y|j}[gcd(x,y)==1] \]

\[\phi(ij)=\frac{\phi(i)\phi(j)gcd(i,j)}{\phi(gcd(i,j))} \]

推柿子参看题解区

然后令\(F(n)=\sum_{i=1}^n\lfloor\frac{n}{i}\rfloor\)，则

\[ans=\sum_{g=1}^{\min(n,m)}\mu(g)\cdot F(\lfloor\frac{n}{g}\rfloor)\cdot F(\lfloor\frac{m}{g}\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\) 可以得到：

\[\sum_{d=1}^{n}F^2(\lfloor \frac{n}{d}\rfloor)\cdot d^2\phi(d) \]

其中 \(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\) ，则有：

\[s(n)=\sum_{i=1}^{n}((id^2 \phi)*g)(i)-\sum_{i=2}^{n}id^2(i)s(\lfloor \frac{n}{i}\rfloor) \]

化简得到：

\[s(n)=(\frac {n\times (n+1)}{2})^2-\sum_{i=2}^{n}i^2s(\lfloor \frac{n}{i}\rfloor) \]

P3312数表

先不考虑 \(a\) 的限制，有：

\[ans=\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{k|gcd(i,j)}k \]

\[=\sum_{i=1}^{n}\sum_{j=1}^{m}f(gcd(i,j)) \]

\[=\sum_{d=1}^{n}\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}f(d)[gcd(i,j)==d] \]

\[=\sum_{d=1}^{n}\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}f(d)\sum_{k|gcd(i,j)}\mu(k) \]

\[=\sum_{d=1}^{n}f(d)\sum_{k=1}^{\lfloor\frac{m}{d}\rfloor}\mu(k)\lfloor\frac{n}{dk}\rfloor\lfloor\frac{m}{dk}\rfloor \]

\[=\sum_{t=1}^{m}\lfloor\frac{n}{t}\rfloor\lfloor\frac{m}{t}\rfloor\sum_{kd=t}\mu(k)f(d) \]

(其中 \(f(x)\) 表示 \(x\) 的因数和，可以预处理得到)

接下来考虑 \(a\) 。首先将询问按照 \(a\) 从小到大排序，然后开一个树状数组（其中单点\(i\)表示 \((f*\mu)(i)\) ），每次遇到可以加入树状数组的 \(f(i)\) ，就枚举 \(i\) 的倍数，令 \(ki\) 的单点数值增加 \(f(i)\times\mu(k)\) 。然后在数论分块的时候，如果当前区间为 \([l,r]\) ，就让 \(ans\) 乘以 \([l,r]\) 的区间和。