由于2<=n<=10^6,所以一般的求欧拉函数方法用不上,而我们可以根据他的一个性质
设a为N的质因数,若(N % a == 0 && (N / a) % a == 0) 则有E(N)=E(N / a) * a;若(N % a == 0 && (N / a) % a != 0) 则有:E(N) = E(N / a) * (a - 1)。
进行求解,而现在首要的任务就是求质因数a,我们可以利用线性筛素数时产生的N最小素数,所以首先又要线性筛素数,这个DD以前听过,但是一直没有用过,今天利用大半个晚上好好学习了这种O(n)筛法,具体可以看我blog。
代码实现:
#include <vector> #include <list> #include <map> #include <set> #include <string.h> #include <deque> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <ctime> using namespace std; #define LL long long #define pi acos(-1) #define N 1000000+10 #define INF 999999999 #define eps 1e-8 //**************************************** //poj 2478 //Copyright@leolin All rights reserved. //**************************************** LL dp[N]; LL num,prime[N/3]; LL min_prime[N]; LL cnt; bool is_prime[N]; void init() { LL i,j,k; memset(is_prime,1,sizeof(is_prime)); cnt=0; for(i=2;i<=N-10;i++) { if(is_prime[i])prime[cnt++]=i; for(j=0;j<cnt && i*prime[j]<=N-10;j++) { k=i*prime[j]; is_prime[k]=0; min_prime[k]=prime[j]; if(i%prime[j]==0) { // printf("%I64d %I64d\n",i,prime[j]); break; } } } } void solve() { LL i,j,k; for(i=2;i<=N-10;i++) { if(!is_prime[i]) { LL minm=min_prime[i]; LL div=i/minm; dp[i]= ( div%minm==0 ? minm*dp[div] : dp[div]*(minm-1) ); } else dp[i]=i-1; } for(i=3;i<=N-10;i++) dp[i]+=dp[i-1]; } int main() { //freopen("a.txt","r",stdin); LL n; init(); solve(); while(scanf("%I64d",&n)&&n) { printf("%I64d\n",dp[n]); } return 0; }