Description

link

给定\(n\),\(m\),\(k\),计算

\[\sum_ {i=1}^n \sum^m_{j=1} gcd(i,j)^k \space mod \space 10^9+7
\]

Solution

这种带着 \(gcd\) 的题目就是要反演对吧

然后我们设：

\[f(n)=n^k=\sum_{d|n} g(d)
\]

\[g(n)=\sum_{d|n} f(d) \mu(\frac{n}{d})
\]

所以我们化简一下原式：

\[\sum_ {i=1}^n \sum^m_{j=1} gcd(i,j)^k
\]

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

\[=\sum_ {i=1}^n \sum^m_{j=1}\sum_{d|gcd(i,j)} g(d)
\]

更换枚举的顺序：（先枚举\(d\)）

\[\sum^{min(n,m)}_ {d=1}\sum_{d|i}^{n}\sum^m_{d|j}\space g(d)
\]

\[\sum^{min(n,m)}_ {d=1} \lfloor\dfrac{n}{d}\rfloor \lfloor \frac{m}{d}\rfloor g(d)
\]

然后经过考虑复杂度的问题，我们只能线性筛\(g(x)\)

这里的具体过程看代码吧

Code

#include<bits/stdc++.h>

using namespace std;

#define int long long

namespace yspm{

	inline int read()

	{

		int res=0,f=1; char k;

		while(!isdigit(k=getchar())) if(k=='-') f=-1;

		while(isdigit(k)) res=res*10+k-'0',k=getchar();

		return res*f;

	}

	const int N=5e6,mod=1e9+7;

	int T,k,pri[N],g[N],tot,f[N];

	bool fl[N];

	inline int ksm(int x,int y)

	{

		int res=1; for(;y;y>>=1){if(y&1) (res*=x)%=mod; (x*=x)%=mod;}

		return res;

	}

	inline void prework()

	{

		f[1]=1;

		for(int i=2;i<N;++i)

		{

			if(!fl[i]) pri[++tot]=i,g[tot]=ksm(i,k),f[i]=(g[tot]-1+mod)%mod;

			for(int j=1;j<=tot&&i*pri[j]<N;++j)

			{

				fl[i*pri[j]]=1;

				if(i%pri[j]==0){f[i*pri[j]]=f[i]*g[j]%mod; break;}

				else{f[i*pri[j]]=f[i]*f[pri[j]]%mod;}

			}

		} for(int i=1;i<N;++i) (f[i]+=f[i-1])%=mod;

		return ;

	}

	inline void work()

	{

		int ans=0,n=read(),m=read(),T=min(n,m);

		for(int l=1,r;l<=T;l=r+1)

		{

			r=min(n/(n/l),m/(m/l));

			ans+=(f[r]-f[l-1]+mod)*(n/l)%mod*(m/l)%mod; ans%=mod;

		}

		return printf("%lld\n",ans),void();

	}

	signed main()

	{

		T=read(); k=read(); prework(); while(T--) work();

		return 0;

	}

}

signed main(){return yspm::main();}

巴特西

LGOJ4449 于神之怒加强版

Description

Solution

Code

最新文章

热门文章