線性求歐拉函數值和篩選素數

線性求歐拉函數值和篩選素數

2818: Gcd

題目：

給定整數N，求1<=x,y<=N且Gcd(x,y)為素數的
數對(x,y)有多少對. 1<=N<=10^7

算法：

求解 g = Gcd(x,y)為素數，轉換問題成x/g,y/g互質。所以，只要求出[1,N/pi]內互質的對數(pi為1....N之間的素數)。枚舉pi就可以了。而這裡就可以用到線性的歐拉求解，普通歐拉為O(nlognlogn)。

/*

線性素數加歐拉篩法O(N)

題目：
   給定整數N，求1<=x,y<=N且Gcd(x,y)為素數的數對(x,y)有多少對.
   
   其實就是一個轉化問題，求gcd(x, y) = k, 1 <= x, y <= n的對數等於：
求gcd(x, y) = 1, 1 <= x, y <= n/k的對數。（在[1,n/k]存在多少個有序對(x,y)使得互質）
那麼接下來我們就只要枚舉每個素數k=prime[i]了，然後用到歐拉函數就可以求出來了，
Σ( 2*Σ( phi[n/prime[i]] ) - 1 )。

N < 10^7 
歐拉函數:phi[n]表示1~n內有多少個數與n互質

*/

typedef long long LL;
const int MAXN  = 10000000 + 10;

int top,primes[700000];
LL phi[MAXN];
int n;

//線性篩歐拉值和素數表
void phi_primes(){
    top = 0; phi[1] = 1;
    for(int i = 2;i <= n;++i){
        if(!phi[i]){
            primes[top++] = i;
            phi[i] = i - 1;
        }
        for(int j = 0;j < top&&i*primes[j] <= n;++j){
            if(i%primes[j])
                phi[i*primes[j]] = phi[i]*(primes[j] - 1);
            else {phi[i*primes[j]] = phi[i]*primes[j]; break;}
        }
    }
}

int main()
{
      scanf("%d",&n);
      phi_primes();
      
       for(int i = 2;i <= n;++i) phi[i] += phi[i-1];  //1...i內互質的總數 

        LL ans = 0;
        for(int i = 0;i < top&&primes[i] <= n;++i){
            ans += (phi[n/primes[i]] << 1)-1;     //除去素數多算的一次
        }
        printf("%lld\n",ans);
    return 0;
}