hdu2824罗选法欧拉函数+求和

hdu2824筛选法欧拉函数+求和

hdu2824

筛选版本的欧拉公式模板

#include<iostream>#define MAX 3000000using namespace std;__int64 E[MAX+10];void init()             //模板 {int i,j;memset(E,0,sizeof(E));E[1]=1;for(i=2;i<=MAX;i++){if(!E[i]){for(j=i;j<=MAX;j+=i){if(!E[j]) E[j]=j;E[j]=E[j]/i*(i-1);}}//E[i]+=E[i-1];}}int main(){int a,b;init();while(scanf("%d%d",&a,&b)!=EOF){if(a>b) swap(a,b);printf("%I64d\n",E[b]-E[a-1]);}return 0;}

Euler(n)个与n互质的数的总和 为 Euler(n)*n/2

又是一道模板题……hdu3501