luogu P3768 简单的数学题

简单的数学题，真是简单。

题目

自己推得比较复杂，但还是推出来了。这里讲个更简洁的做法。

(sum_{i=1}^n sum_{j=1}^n ijgcd(i,j))

(=sum_{i=1}^n sum_{j=1}^n ijsum_{d|i,d|j} varphi(d)) //注意这一步

(=sum_{d=1}^n varphi(d)sum_{d|i}sum_{d|j}ij)

(=sum_{d=1}^n varphi(d)d^2(sum_{i=1}^{lfloorfrac{n}{d} floor}i)^2)

后面这个 ((sum_{i=1}^{lfloorfrac{n}{d} floor}i)^2) 显然可以 (O(1)) 求出。

而这个 (sumvarphi(x)x^2) 可以杜教筛。

怎么杜教筛？

取 (g(x)=x^2)，则 (fcirc g=x^3)。

而：

(sum_{i=1}^n x=frac{n(n+1)}{2})；

(sum_{i=1}^n x^2=frac{n(n+1)(2n+1)}{6})；

(sum_{i=1}^n x^3=(frac{n(n+1)}{2})^2)。

除法分块即可。容易证明，复杂度为 (O(n^{frac{2}{3}}))。

NOI2010 能量采集(题目)也可以这样做，更简单。

#include<cstdio>
#include<map>
typedef long long ll;
const ll D=1e7+3;
ll n,M,INV2,INV6,f[D],p[D],np[D],k,ans;
inline ll S1(ll n){n%=M;return n*(n+1)%M*INV2%M;}
inline ll S2(ll n){n%=M;return n*(n+1)%M*(n+n+1)%M*INV6%M;}
inline ll S3(ll n){n%=M;return S1(n)*S1(n)%M;}
inline ll Pow(ll a,ll m){ll s=1;for(;m;m>>=1)m&1?s=s*a%M:0,a=a*a%M;return s;}
std::map<ll,ll>sf;
ll Sf(ll n){
	if(n<D)return f[n];
	if(sf[n])return sf[n];
	ll s=S3(n);
	for(ll i=2,j;i<=n;i=j+1){
	  j=n/(n/i);
	  s=(s-Sf(n/i)*(S2(j)-S2(i-1)+M)+M)%M;
	}return sf[n]=s;
}
int main(){
	f[1]=1;
	for(ll i=2;i<D;i++){
	  if(!np[i])p[++k]=i,f[i]=i-1;
	  for(ll j=1;j<=k&&i*p[j]<D;j++){
		np[i*p[j]]=1;
		if(i%p[j])f[i*p[j]]=f[i]*(p[j]-1);
		else{f[i*p[j]]=f[i]*p[j];break;}
	  }
	}
	scanf("%lld%lld",&M,&n);
	for(ll i=1;i<D;i++)f[i]=(f[i-1]+i*i%M*f[i])%M;
	INV2=Pow(2,M-2),INV6=Pow(6,M-2);
	for(ll i=1,j;i<=n;i=j+1){
	  j=n/(n/i);
	  ans=(ans+(S3(j)-S3(i-1)+M)*Sf(n/i))%M;
	}printf("%lld",ans);
	return 0;
}