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;
}