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 欧拉函数之和

相关文章