题解 SP3871 【GCDEX - GCD Extreme】

周道_Althen · 2018-10-26 19:58:30 · 题解

我们要求的式子：

\sum_{i=1}^{n}\sum_{j=i+1}^{n}{\rm gcd}(i,j)

令：g(n)=\sum_{i=1}^{n-1}{\rm gcd}(i,n)

那么答案就是：\sum_{i=1}^{n}g(n)

现在我们逐步化简：

\begin{aligned}g(n)&=\sum_{i=1}^{n-1}{\rm gcd}(i,n)\\&=\sum_{d|n}d\times\sum_{i=1}^{n-1}[{\rm gcd}(i,n)=d]\\&=\sum_{d|n}d\times\sum_{i=1}^{\frac{n}{d}-1}[{\rm gcd}(i,\frac{n}{d})=1]\\&=\sum_{d|n}d\times\varphi\left(\frac{n}{d}\right)\end{aligned}

(注意本题的特殊性，我们需要重新定义\varphi(1)=0)

容易观察出，g(d)可以用类似于埃式筛法的方法O(n{\rm log}n)筛出。

预处理前缀和，就可以做到O(1)询问，总复杂度O(n{\rm log}n+T)。

那么这道题就完结撒花啦。

#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<cstdio>
#include<vector>
#include<string>
#include<queue>
#include<stack>
#include<cmath>
#include<map>
#include<set>
using namespace std;
const int inf=0x7fffffff;
const double eps=1e-10;
const double pi=acos(-1.0);
//char buf[1<<15],*S=buf,*T=buf;
//char getch(){return S==T&&(T=(S=buf)+fread(buf,1,1<<15,stdin),S==T)?0:*S++;}
inline int read(){
    int x=0,f=1;char ch;ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f=0;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch&15);ch=getchar();}
    if(f)return x;else return -x;
}
const int N=1000010; 
bool vis[N];
long long prim[N],phi[N],ans[N];
void get_phi(int n){
  phi[1]=0;
  for(int i=2;i<=n;i++){
    if(!vis[i]){phi[i]=i-1;prim[++prim[0]]=i;}
    for(int j=1;j<=prim[0]&&i*prim[j]<=n;j++){
      vis[i*prim[j]]=1;
      if(i%prim[j]==0){phi[i*prim[j]]=phi[i]*prim[j];break;}
      else phi[i*prim[j]]=phi[i]*(prim[j]-1);
    }
  }
  for(int i=1;i<=n;i++)ans[i]=phi[i];
  for(int i=2;i*i<=n;i++){
    ans[i*i]+=phi[i]*i;
    for(int j=i+1;j*i<=n;j++)
    ans[j*i]+=phi[i]*j+phi[j]*i;
  }
  ans[1]=0;
  for(int i=2;i<=n;i++)ans[i]+=ans[i-1];
}
int n;
int main()
{
    get_phi(1000000);
  while(scanf("%d",&n)==1&&n){printf("%lld\n",ans[n]);}
    return 0;
}

先不着急，我们来看看另一种算法为什么会\color{#00E}{\tt TLE}。比如说UVA11426 GCD - Extreme (II)的算法。

我们要求的式子：

\sum_{i=1}^{n}\sum_{j=i+1}^{n}{\rm gcd}(i,j)

现在我们逐步化简：

\begin{aligned}\sum_{i=1}^{n}\sum_{j=i+1}^{n}{\rm gcd}(i,j)&=\sum_{j=1}^{n}\sum_{i=1}^{j-1}{\rm gcd}(i,j)\\&=\sum_{d=1}^{n}d\times \sum_{j=1}^{n}\sum_{i=1}^{j-1}\left[{\rm gcd}(i,j)=d\right]\\&=\sum_{d=1}^{n}d\times \sum_{j=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\sum_{i=1}^{j-1}\left[{\rm gcd}(i,j)=1\right]\\&=\sum_{d=1}^{n}d\times \sum_{j=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\varphi(j)\end{aligned}

运用数论分块，我们可以做到O(n+T\sqrt n)的复杂度。仔细算一算，发现……确实有点卡……，但是O(n{\rm log}n+T)也没有比O(n+T\sqrt n)好多少。~~（毒瘤）~~

不过，你要是都已经算到这一步了，还有一种方法可以得到我们理想的答案。

已知：\sum_{i=1}^{n}\sum_{j=i+1}^{n}{\rm gcd}(i,j)=\sum_{d=1}^{n}d\times \sum_{j=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\varphi(j)

我们做差：

{\color{#F00}{X}}=\sum_{d=1}^{n}d\times \sum_{j=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\varphi(j)-\sum_{d=1}^{n-1}d\times \sum_{j=1}^{\left\lfloor\frac{n-1}{d}\right\rfloor}\varphi(j)

令：

{\rm size}(n,x)=\sum_{i=1}^{n}i\times\left[\left\lfloor \frac{n}{i}\right\rfloor\geq x\right]

代表在输入为n时，\varphi(x)被计算了多少次。

容易得到：

\begin{aligned}{\color{#F00}{X}}&=\sum_{d=1}^{n}d\times \sum_{j=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\varphi(j)-\sum_{d=1}^{n-1}d\times \sum_{j=1}^{\left\lfloor\frac{n-1}{d}\right\rfloor}\varphi(j)\\&=\sum_{i=1}^{n}\varphi(i)\times\left({\rm size}(n,i)-{\rm size}(n-1,i)\right)\\&=\sum_{x=1}^{n}\varphi(x)\times\left(\sum_{i=1}^{n}i\times\left[\left\lfloor \frac{n}{i}\right\rfloor\geq x\right]-\sum_{i=1}^{n}i\times\left[\left\lfloor \frac{n-1}{i}\right\rfloor\geq x\right]\right)\\&=\sum_{x=1}^{n}\varphi(x)\times\left(\sum_{i=1}^{n}i\times\left(\left[\left\lfloor \frac{n}{i}\right\rfloor\geq x\right]-\left[\left\lfloor \frac{n-1}{i}\right\rfloor\geq x\right]\right)\right)\end{aligned}

已知n和n-1是互质的，且n>n-1，所以只有当i是n因数时，\lfloor\frac{n-1}{i}\rfloor=(\lfloor \frac{n}{i}\rfloor-1)\neq\lfloor \frac{n}{i}\rfloor；其他情况下，无论i与n-1的关系，\lfloor\frac{n-1}{i}\rfloor=\lfloor \frac{n}{i}\rfloor。

所以有：

\begin{aligned}{\color{#F00}{X}}&=\sum_{x=1}^{n}\varphi(x)\times\left(\sum_{i=1}^{n}i\times\left(\left[\left\lfloor \frac{n}{i}\right\rfloor\geq x\right]-\left[\left\lfloor \frac{n-1}{i}\right\rfloor\geq x\right]\right)\right)\\&=\sum_{x|n}\varphi(x)\times\left(\sum_{i=1}^{n}i\times\left(\left[\left\lfloor \frac{n}{i}\right\rfloor\geq x\right]-\left[\left\lfloor \frac{n-1}{i}\right\rfloor\geq x\right]\right)\right)\\&=\sum_{x|n}\varphi(x)\times i\times\left(\left[\left\lfloor \frac{n}{i}\right\rfloor\geq x\right]-\left[\left\lfloor \frac{n-1}{i}\right\rfloor\geq x\right]\right)\ \ \ \ \ (i=\frac{n}{x})\\&=\sum_{x|n}\varphi(x)\times i\times\left(\left[\left\lfloor \frac{n}{i}\right\rfloor\geq x\right]-\left[\left\lfloor \frac{n}{i}\right\rfloor-1\geq x\right]\right)\ \ \ \ \ (i=\frac{n}{x})\\&=\sum_{x|n}\varphi(x)\times i\times\left(\left[x\geq x\right]-\left[x-1\geq x\right]\right)\ \ \ \ \ (i=\frac{n}{x})\\&=\sum_{x|n}\varphi(x)\times i\ \ \ \ \ (i=\frac{n}{x})\\&=\sum_{x|n}\varphi(x)\times \frac{n}{x}\end{aligned}

所以有：

\sum_{d=1}^{n}d\times \sum_{j=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\varphi(j)=\sum_{d=1}^{n}d\times \sum_{j=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\varphi(j)+{\color{#F00}{\sum_{x|n}\varphi(x)\times \frac{n}{x}}}

然后我们就得到上面的式子啦:

\sum_{d=1}^{n}\sum_{d'|d}d\times\varphi\left(\frac{d}{d'}\right)

最后推荐几道题，7倍经验的哦！

UVA11417 GCD；

UVA11424 GCD - Extreme (I)；

UVA11426 GCD - Extreme (II)；

P1390 公约数的和；

P2398 GCD SUM；

P2568 GCD；

SP3871 GCDEX - GCD Extreme。