/*
分析:
欧拉函数。
才刚开始看那么一点儿数论,菜的不可思议~。欧拉函数
果题,没什么要多说的。
有点儿小无语的是,看到有300W的数据量,就想用数据
结构优化下,以便能迅速得到a到b之间的所有phi,但是想来
想去也会MLE的,于是无奈的看了下别人的代码,没想到。。。
竟然是暴力遍历求的sum,数据弱么。。。。
2012-11-21
*/
#include"stdio.h" #include"string.h" #include"stdlib.h" #define N 3000011 int phi[N]; void getphi() { int i,j; phi[1]=1; for(i=2;i<=3000000;i++) phi[i]=i; for(i=2;i<=3000000;i++) { if(i==phi[i]) { for(j=i;j<=3000000;j+=i) { phi[j]=phi[j]/i*(i-1); } } } } int main() { int a,b; int i; __int64 ans; getphi(); while(scanf("%d%d",&a,&b)!=-1) { ans=0; for(i=a;i<=b;i++) ans+=phi[i]; printf("%I64d\n",ans); } return 0; }