[SDOI2008]儀仗隊

題意：設左下方是坐標 ( 0 , 0 ) (0,0) (0,0)，求( 0 , 0 ) 0,0) 0,0)處能夠看到的人數，

每個人對應一個坐標 ( x , y ) (x,y) (x,y)，只要 g c d ( x , y ) = 1 gcd(x, y)=1 gcd(x,y)=1就能被 ( 0 , 0 ) (0,0) (0,0)看到（令 g c d ( 0 , 1 ) = 1 gcd(0,1)=1 gcd(0,1)=1,和 ? ( 1 ) = 1 對 應 \phi(1)=1對應 ?(1)=1對應），

歐拉函式

思路：我們只看其中的一半x，另一半和它對稱，然后就得到式子 x = ∑ x = 1 n ∑ y = 1 x [ g c d ( x , y ) = 1 ] x=\sum_{x=1}^n\sum_{y=1}^x[gcd(x,y)=1] x=∑x=1n?∑y=1x?[gcd(x,y)=1]

推式子：

∑ x = 1 n ∑ y = 1 i [ g c d ( x , y ) = 1 ] ∑ x = 1 n ? ( x ) \sum_{x=1}^n\sum_{y=1}^i[gcd(x,y)=1]\\ \sum_{x=1}^n\phi(x)\\ x=1∑n?y=1∑i?[gcd(x,y)=1]x=1∑n??(x)
? ( x ) \phi(x) ?(x)可以提前用線性篩篩出來，然后再求 ? ( x ) \phi(x) ?(x)的前n項和x，答案就是2*x+1了（這里的1是 g c d ( 1 , 1 ) = 1 gcd(1,1)=1 gcd(1,1)=1），

我們是從 x = 1 ， y = 1 x=1，y=1 x=1，y=1開始列舉，但看起來 g c d ( 0 , 1 ) 和 g c d ( 1 , 0 ) gcd(0,1)和gcd(1,0) gcd(0,1)和gcd(1,0)并沒有算進去，其實x的計算中 ? ( 1 ) 其 實 已 經 把 這 些 算 進 去 了 \phi(1)其實已經把這些算進去了 ?(1)其實已經把這些算進去了

C o d e Code Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e6;
bool st[N];
ll p[N], ou[N], tot;
//歐拉函式的線性篩
void init() {
    for(int i=2; i<N; i++) {
        if(!st[i]) {
            p[tot++] = i;
            ou[i] = i-1;
        }
        for(int j=0; j<tot&&i*p[j]<N; j++) {
            st[i*p[j]] = 1;
            if(i % p[j] == 0) {
                ou[i*p[j]] = ou[i]*p[j];
                break;
            }
            ou[i*p[j]] = ou[i]*(p[j]-1);
        }
    }
}
int main() {
    ou[1] = 1;
    init();
    ll n, ans = 0;
    cin >> n;
    //求歐拉函式前n-1項的和
    //為啥是n-1,因為是從坐標（0，0）開始計算的，
    for(int i=1; i<n; i++) {
        ans += ou[i];
    }
    cout << ans*2+1;
    return 0;
}

莫比烏斯反演

推式子：

∑ i = 1 n ∑ j = 1 n [ g c d ( i , j ) = 1 ] ∑ i = 1 n ∑ j = 1 n ∑ d ∣ g c d ( i , j ) μ ( d ) ∑ d = 1 n ∑ i = 1 n ∑ j = 1 n ∑ d ∣ g c d ( i , j ) μ ( d ) ∑ d = 1 n μ ( d ) ∑ i = 1 n d ∑ j = 1 n d 1 ∑ d = 1 n μ ( d ) ? n d ? ? n d ? \sum_{i=1}^{n}\sum_{j=1}^n[gcd(i,j)=1]\\ \sum_{i=1}^n\sum_{j=1}^n\sum_{d|gcd(i,j)}\mu(d)\\ \sum_{d=1}^n\sum_{i=1}^n\sum_{j=1}^n\sum_{d|gcd(i,j)}\mu(d)\\ \sum_{d=1}^n\mu(d)\sum_{i=1}^{\frac nd}\sum_{j=1}^{\frac nd}1\\ \sum_{d=1}^n\mu(d)\lfloor\frac nd\rfloor\lfloor\frac nd\rfloor i=1∑n?j=1∑n?[gcd(i,j)=1]i=1∑n?j=1∑n?d∣gcd(i,j)∑?μ(d)d=1∑n?i=1∑n?j=1∑n?d∣gcd(i,j)∑?μ(d)d=1∑n?μ(d)i=1∑dn??j=1∑dn??1d=1∑n?μ(d)?dn???dn??
從上往下解釋一下：
第一個式子是總的答案；
第二個式子是莫比烏斯函式的一個性質；
第三個式子加了一個列舉d的操作，這樣的話就可以轉換成第四個式子；
第四個式子（比較重要）d是i，j的因子所以可以寫成 ∑ d ∣ i , d ∣ j \sum_{d|i,d|j} ∑d∣i,d∣j?說明d是i，j的因子，同樣也說明i，j是d的因子，在區間 [ 1 , n ] [1,n] [1,n]中是d的倍數的有 n d \frac nd dn?個，同樣也是第五個式子，

然后看到 n d \frac nd dn?就可以想到整除分塊了，

C o d e Code Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e6+10;
ll p[N], sum[N], phi[N], tot, mu[N];
bool st[N];
//線性篩篩出莫比烏斯函式
void init() {
   phi[1] = 1, mu[1] = 1;
   for(int i=2; i<N; i++) {
      if(!st[i]) p[tot++] = i, phi[i] = i-1, mu[i] = -1;
      for(int j=0; j<tot&&i*p[j]<N; j++) {
         st[i*p[j]] = 1;
         if(i % p[j] == 0) {
            phi[i*p[j]] = phi[i]*p[j];
            mu[i*p[j]] = 0;
            break;
         }
         phi[i*p[j]] = phi[i]*(p[j]-1);
         mu[i*p[j]] = -mu[i];
      }
   }
   //對莫比烏斯函式求前綴和
   for(int i=1; i<N; i++) {
      sum[i] = sum[i-1] + mu[i];
   }
}

ll solve(ll n, ll m) {//整除分塊（模板）
   ll ans = 0;
   if(n > m) swap(n, m);
   for(ll i=1, last; i<=n; i=last+1) {
      last = min(n/(n/i), m/(m/i));
      ans += 1ll*(n/i)*(m/i)*(sum[last]-sum[i-1]);
   }
   return ans;
}
int main() {
   init();
   ll n, m;
   cin >> n;
   cout << solve(n-1, n-1)+2;
   return 0;
}

E n d End End