Uva11424 GCD - Extreme (I) 欧拉函数的应用 - c++编程基础

这道题目的方法跟 UVA11426是一模一样，但是求欧拉函数值的模版要换一换，11426求欧拉函数值的模版不能用线性的，因为会爆内存，而这道n只有2 00 000这么大，所以不用担心内存，同时又有20000测试案例，所以一定要用线性，不然会超时的，解析过程就是一模一样的，

设f(n)=gcd(1,n)+gcd(2,n)+....+gcd(n-1,n),则所求的答案为 s(n)=f(1)+f(2)+...+f(n),因为这个式子可以变成递推式 s(n)=s(n-1)+f(n),同时又可以找到边界条件 f[2]==s[2],所以只需要求出f(n);

用g(n,i)表示满足 gcd(x,n)=i的 x的个数（x小于n），则 f(n)=sum{i*g(n,i)};

同时又利用扩展欧几里德的性质 gcd(x,n)=i 的充要条件是 gcd(x/i,n/i)==1，所以满足 x/i的解有 phi(n/i)个，说明 g(n,i)=phi(n/i),

#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
  
#define ll long long  
#define LL __int64  
#define eps 1e-8  
  
#define inf 0xfffffff  
  
using namespace std;  
  
  
//vector > G;  
//typedef pair




 P;  
//vector> ::iterator iter;  
//  
//mapmp;  
//map::iterator p;  
//  
//vectorG[30012];  
  
const int maxp = 1000000 + 5;  
  
ll pri[maxp], phi[maxp], pnum;  
bool vis[maxp];  
  
void phi_table(int n){  
    pnum = 0;  
    phi[1] = 1;  
    for(int i = 2;i <= n; i++){  
        if(!vis[i]) {  
            pri[pnum++] = i;  
            phi[i] = i-1;  
        }  
        for(int j = 0;j < pnum; j++) {  
            if(i*pri[j] > n)    break;  
            vis[i * pri[j]] = true;  
            if(i % pri[j] == 0) {  
                phi[i*pri[j]] = phi[i]*pri[j];  
                break;  
            }  
            phi[i * pri[j]] = phi[i]*(pri[j] - 1);  
        }  
    }  
}  
  
ll f[maxp],s[maxp];  
  
void init()  
{  
    for(int i=1;i>n,n)  
    {  
        cout<