BZOJ 4176: Lucas的数论莫比乌斯反演 + 杜教筛

短命女 2021-11-17 16:26 219阅读 0赞

## Description ##

去年的Lucas非常喜欢数论题，但是一年以后的Lucas却不那么喜欢了。

在整理以前的试题时，发现了这样一道题目“求Sigma(f(i)),其中1<=i<=N”，其中 表示i的约数个数。他现在长大了，题目也变难了。

求如下表达式的值：

![abc.jpg][]

其中 表示ij的约数个数。

他发现答案有点大，只需要输出模1000000007的值。

## Input ##

第一行一个整数n。

## Output ##

一行一个整数ans，表示答案模1000000007的值。

题解：

\[SDOI2015\]约数个数和 得出的结论：

$Ans=\\sum\_\{d=1\}^\{n\}\\mu(d)\\sum\_\{x=1\}^\{\\left \\lfloor \\frac\{n\}\{d\} \\right \\rfloor\}\\left \\lfloor \\frac\{n\}\{xd\} \\right \\rfloor\\sum\_\{y=1\}^\{\\left \\lfloor \\frac\{m\}\{d\} \\right \\rfloor\}\\left \\lfloor \\frac\{m\}\{yd\} \\right \\rfloor$

这里 $n,m$ 相等

$\\Rightarrow Ans=\\sum\_\{d=1\}^\{n\}\\mu(d)(\\sum\_\{x=1\}^\{\\left \\lfloor \\frac\{n\}\{d\} \\right \\rfloor\}\\left \\lfloor \\frac\{n\}\{xd\} \\right \\rfloor)^2$

由于 $n<=10^9$ , 需要用杜教筛来算 $\\sum\_\{i=1\}^\{n\}\\mu(i)$

后面的 $(\\sum\_\{x=1\}^\{\\left \\lfloor \\frac\{n\}\{d\} \\right \\rfloor\}\\left \\lfloor \\frac\{n\}\{xd\} \\right \\rfloor)^2$ 直接暴力计算就行.

#include<bits/stdc++.h>
    #define setIO(s) freopen(s".in","r",stdin) 
    #define maxn 10000004 
    #define M 5000001 
    #define ll long long
    using namespace std;
    const long long mod = 1000000007; 
    int cnt; 
    ll sumv[maxn]; 
    bool vis[maxn]; 
    int prime[maxn], mu[maxn]; 
    inline void Linear_shaker()
    {
    	mu[1]=1; 
    	int i,j; 
    	for(i=2;i<=M;++i)
    	{
    		if(!vis[i]) prime[++cnt]=i, mu[i]=-1; 
    		for(j=1;j<=cnt&&1ll*i*prime[j]<=M;++j) 
    		{
    			vis[i*prime[j]]=1; 
    			if(i%prime[j]==0) 
    			{
    				mu[i*prime[j]]=0; 
    				break; 
    			}
    			mu[i*prime[j]]=-mu[i]; 
    		}
    	}
    	for(i=1;i<=M;++i) sumv[i]=(sumv[i-1]+1ll*mu[i]+mod)%mod;   
    }
    inline ll Sum(ll n)
    {
    	ll i,j,re=0; 
    	for(i=1;i<=n;i=j+1)
    	{
    		j=n/(n/i); 
    		re+=(j-i+1)%mod*(n/i)%mod; 
    		re%=mod; 
    	}
    	return re;   
    }
    map<int,ll>ansmu; 
    ll Get(ll n)
    {
    	if(n<=M) return sumv[n]; 
    	if(ansmu[n]) return ansmu[n];  
    	ll i,j,re=0; 
    	for(i=2;i<=n;i=j+1)
    	{
    		j=n/(n/i); 
    		re=(re+(j-i+1ll*1)%mod*(Get(n/i))%mod)%mod;  
    	}
    	return ansmu[n]=(1ll-re+mod)%mod; 
    }
    int main()
    {
    	// setIO("input"); 
    	Linear_shaker(); 
    	ll i,j,re=0; 
    	int n; 
    	scanf("%d",&n);    
    	for(i=1;i<=n;i=j+1)
    	{
    		j=n/(n/i); 
    		re=(re+((Get(j)-Get(i-1)+mod)%mod*Sum(n/i)%mod*Sum(n/i)%mod)%mod)%mod; 
    	}
    	printf("%lld\n",re); 
    	return 0; 
    }

转载于:https://www.cnblogs.com/guangheli/p/11102654.html

[abc.jpg]: https://www.lydsy.com/JudgeOnline/upload/201507/abc.jpg