POJ - 2478 Farey Sequence （歐拉函數）

原題連結：傳送門

題意：給你一個函數 F()，F(n) 就是 1-n 之内兩個數 gcd(a，b) = 1 的總個數。

思路：很顯然，是求歐拉函數的。

F(n) = F(n-1) + phi[i]

，直接套歐拉函數模闆。

// #include <bits/stdc++.h>
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long ll;
const int N = 1e6+10;
int book[N],prime[N];
int phi[N];
ll F[N];
int cnt;

void Eular(){	//線性篩歐拉函數
    cnt = 0;
    memset(book,0,sizeof(book));
    phi[1] = 1;
    for(int i=2;i<N;i++){
        if(!book[i]){
            prime[cnt++] = i;
            phi[i] = i-1;	//若a為質數,phi[a]=a-1;
        }
        for(int j=0;j<cnt;j++){
            if(i*prime[j] > N)
                break;
            book[i*prime[j]] = 1;
            if(i%prime[j] == 0)
                phi[i*prime[j]] = phi[i] * prime[j];	//若a為質數,b mod a=0,phi[a*b]=phi[b]*a
            else phi[i*prime[j]] = phi[i] * (prime[j]-1);	
            //若a,b互質,phi[a*b]=phi[a]*phi[b](當a為質數時,if b mod a!=0 ,phi[a*b]=phi[a]*phi[b])
        }
    }
    // for(int i=1;i<N;i++){
    //     printf("%d\n",phi[i]);
    // }
}

void init(){
    Eular();
    F[1] = 0;
    for(int i=2;i<N;i++){
        F[i] = F[i-1] + phi[i];
    }
}

int main(){
    int n;
    init();
    while(~scanf("%d",&n),n){
        printf("%lld\n",F[n]);
    }
    
	return 0;
}