bzoj4916

链接:bzoj4916

题解

• 显然第一问答案是1,第二问求$S(n)=\sum_{i=1}^n{i*\phi{i}}$
• 设$f(i)=i*\phi(i)$
• 根据杜教筛的套路$\sum_{i=1}^n{h(i)}=\sum_{i=1}^n(f*g)(i)=\sum_{i=1}^n{\sum_{d|i}{f(d) * g(\frac {i}{d})}}=\sum_{i=1}^n{\sum_{d|i}{i * \phi(i) * g(\frac {i}{d})}}$
• 设$g(i)=i$
• 则$\sum_{i=1}^n{h(i)}=\sum_{i=1}^n{i * \sum_{d|i}{\phi(\frac {i}{d})}}$
• 显然$\sum_{i=1}^n{h(i)}=\sum_{i=1}^n{i^2}=\frac {n*(n+1)*(2*n+1)}{6}$
• $$g(1) * S(n)=\sum_{i=1}^nh(i)-\sum_{i=2}^n{\sum_{d|i}{d * \phi(d) * \frac {i}{d}}}=\sum_{i=1}^nh(i)-\sum_{i=2}^n{\sum_{j=1}^{i * j<=n}{j * \phi(j) * i}}$$
• 即$g(1) * S(n)=\frac {n*(n+1)*(2*n+1)}{6}-\sum_{i=2}^n{i * S(\frac {n}{i})}$

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<map>
#include <tr1/unordered_map>
#include<algorithm>
#define rep(i,x,y) for(register int i=x;i<=y;++i)
#define repd(i,x,y) for(register int i=x;i>=y;--i)
#define ll long long
#define get(l,r) ((l+r)*(r-l+1)%mod*p2%mod)
using namespace std;
using namespace std::tr1;
const int N=1e6+7;
const ll mod=1e9+7;
unordered_map<ll,ll> f;
int m=1e6,vis[N],cnt;
ll s[N],phi[N],p[N],p1,p2,n;
ll qpow(ll a,ll b){
	ll res=1;
	while(b){
		if(b&1)res=(res*a)%mod;
		a=a*a%mod;
		b>>=1;
	}
	return res;
}
void pre(){
	phi[1]=1;
	rep(i,2,m){
		if(!vis[i])p[++cnt]=i,phi[i]=i-1;
		for(int j=1;j<=cnt&&p[j]*i<=m;++j){
			vis[p[j]*i]=1;
			if(i%p[j]==0){
				phi[i*p[j]]=p[j]*phi[i];
				break;
			}
			phi[i*p[j]]=(p[j]-1)*phi[i];
		}
	}
	rep(i,1,m)s[i]=(phi[i]*i%mod+s[i-1])%mod;
}
ll solve(ll x){
	if(x<=m)return s[x];
	if(f.count(x))return  f[x];
	ll res=x*(x+1)%mod*(x*2+1)%mod*p1%mod;
	for(ll l=2,r=2;l<=x;l=r+1){
		r=x/(x/l);
		res=(res-get(l,r)*solve(x/l)%mod+mod)%mod;
	}
	return f[x]=res;
}
int main(){
	pre();
	while(~scanf("%lld",&n)){
		p1=qpow(6,mod-2);p2=qpow(2,mod-2);
		printf("1\n%lld\n",solve(n));
	}
	return 0;
}