51nod1239 欧拉函数之和

跟1244差不多。

//由于（x+1）没有先mod一下一直WA三个点我。。。

//由于（x+1）没有先mod一下一直WA三个点我。。。 
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
using namespace std;
#define rep(i,s,t) for(ll i=s;i<=t;i++)
#define dwn(i,s,t) for(ll i=s;i>=t;i--)
#define clr(x,c) memset(x,c,sizeof(x))
#define qwq(x) for(edge *o=head[x];o;o=o->next)
#define ll long long
const ll md=1e6+7;
const ll mod=1e9+7;
const int nmax=6e6+5;
struct edge{
	ll to,dis;edge *next;
};
edge es[md<<1],*pt=es,*head[md];
ll pi[nmax+1];int pe[nmax+1];bool vis[nmax+1];
void add(ll u,ll v,ll d){
	pt->to=v;pt->dis=d;pt->next=head[u];head[u]=pt++;
}
const ll zs=500000004;
ll get(ll x){
	if(x<=nmax) return pi[x];
	ll tp=x%md;qwq(tp) if(o->to==x) return o->dis;
	ll ans=0,last;
	for(ll i=2;i<=x;i=last+1){
		last=x/(x/i);
		ans=(ans+(last-i+1)%mod*get(x/i)%mod)%mod;
	}
	ll orz=(x%mod*((x+1)%mod)%mod*zs%mod-ans+mod)%mod;
	add(tp,x,orz);
	return orz;
}
int main(){
	pi[1]=1;int cnt=0,tp;
	rep(i,2,nmax){
		if(!vis[i]) pe[++cnt]=i,pi[i]=i-1;
		rep(j,1,cnt){
			tp=pe[j];if(i*tp>nmax) break;vis[i*tp]=1;
			if(i%tp==0){
				pi[i*tp]=pi[i]*tp;break;
			} pi[i*tp]=pi[i]*pi[tp];
		}
	}
	rep(i,2,nmax) pi[i]=(pi[i]+pi[i-1])%mod;
	ll n;scanf("%lld",&n);
	printf("%lld\n",get(n));
	return 0;
}

1239 欧拉函数之和 51nod1239 欧拉函数之和

基准时间限制：3 秒空间限制：131072 KB 分值: 320 难度：7级算法题

关注

对正整数n，欧拉函数是小于或等于n的数中与n互质的数的数目。此函数以其首名研究者欧拉命名，它又称为Euler's totient function、φ函数、欧拉商数等。例如：φ(8) = 4（Phi(8) = 4），因为1,3,5,7均和8互质。

S(n) = Phi(1) + Phi(2) + ...... Phi(n)，给出n，求S(n)，例如：n = 5，S(n) = 1 + 1 + 2 + 2 + 4 = 10，定义Phi(1) = 1。由于结果很大，输出Mod 1000000007的结果。

Input

输入一个数N。(2 <= N <= 10^10)

Output

输出S(n) Mod 1000000007的结果。

Input示例

Output示例

秒客网

51nod1239 欧拉函数之和

相关文章