UVA – 11426 GCD – Extreme (II)

题目链接

给数n,求出所有gcd(i,j) (i<j<=n)的和.

对两个互质的数i,j,即gcd(i,j)=1,给它们都添加一个因子2,则有gcd(2i,2j)=2. 于是有gcd(ki,kj)=k.
求出所有互质的数对,然后就能进一步求出题目所需要的结果了.

用欧拉函数求出i以内与之互质的数的个数,并打表记录s=i*j内所有的数对i,j的gcd和:
sum[i*j]+=j*phi[i]

最后弄个前缀和,就能快速查询结果了.

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

int phi[4000005];
long long sum[4000005];
void euler(int n){
  for(int i=2;i<=n;++i) phi[i]=i;
  for(int i=2;i<=n;++i){
    if(phi[i]==i){
      for(int j=i;j<=n;j+=i){
        phi[j]=phi[j]/i*(i-1);
      }
    }
    for(int j=1;i*j<=n;++j){
      sum[j*i]+=j*phi[i];
    }
  }
  for(int i=1;i<=n;++i){
    sum[i]+=sum[i-1];
  }
}

int main() {
  //freopen("in.txt","r",stdin);
  //freopen("out.txt","w",stdout);
  int n;
  euler(4000000);
  while(cin>>n&&n){
    cout<<sum[n]<<endl;
  }
  return 0;
}