51nod1239 欧拉函数之和

时间:2022-06-08 19:12:59

跟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;
}

  

基准时间限制:3 秒 空间限制:131072 KB 分值: 320  难度:7级算法题
51nod1239 欧拉函数之和 收藏
51nod1239 欧拉函数之和 关注
对正整数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示例
5
Output示例
10
相关问题
欧拉函数