UVA11426 - GCD - Extreme (II)(數論，歐拉函數）

題目連結：GCD - Extreme (II) - UVA 11426 - Virtual Judge (vjudge.net)​​​​​

題意

給一個數N，求：

其中

，多組輸入，輸入以0結束，保證答案在long long範圍内。

思路

很好的一道題，值得一刷！！！

看的第一眼确實直接往莫比烏斯反演上想，但其實沒那麼複雜......

設

也即記作：

則答案為

也即記作： 

 是以要先求出

，那麼即可通過字首和所有的

，其中

那麼怎麼求

呢？

令

，枚舉因數

，那麼設共有

個

使得

，則對答案的貢獻是

。

接下來考慮怎麼求k。由

則一定有

，且滿足

，即

與

互質。

是以有對任意一個有最大公因數的

一定有一對

與之對應，而

與

互質，是以根據歐拉函數，這樣的

共有

 ，則這樣的

共有

，則每對

對答案的貢獻是

​​​​​​​.

則對于給定的N，歐拉函數

可以在

的時間複雜度算出來，對枚舉的因數

的時間複雜度為

​​​​​​​，字首和求出答案的時間複雜度為

，故計算答案的時間複雜度為

。

AcCode

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 4e6 + 5;
int p[N], phi[N], cnt;
bool vis[N];
LL f[N], s[N];

void get_phi() {
  phi[1] = 1;
  for(int i = 2; i < N; i++) {
    if(!vis[i]) {
      p[++cnt] = i;
      phi[i] = i - 1;
    }
    for(int j = 1; j <= cnt && p[j] * i < N; j++) {
      int m = i * p[j];
      vis[m] = 1;
      if(i % p[j] == 0) {
        phi[m] = p[j] * phi[i];
        break;
      } else {
        phi[m] = (p[j] - 1) * phi[i];
      }
    }
  }
}

signed main(){
  get_phi();
  for(int i = 1; i < N; i++){
    for(int j = i * 2; j < N; j += i){
      f[j] += i * phi[j / i];
    }
  }

  for(int i = 1; i < N; i++){
    s[i] = s[i - 1] + f[i];
  }
  
  LL n;
  while(scanf("%lld", &n) && n){
    printf("%lld\n", s[n]);
  }
  
  return 0;
}