题解 UVA11426 【GCD - Extreme (II)】

岚雪

2018-10-16 16:20:26

Solution

对于原题中要求的式子$\displaystyle{\sum_{i=1}^n\sum_{j=i+1}^n\text{gcd}(i,j)}$,我们对其变形,得到$\displaystyle{\sum_{i=1}^n\sum_{j=1}^{i-1}\text{gcd}(i,j)}$。 下面问题转换为求$\displaystyle{\sum_{i=1}^n\sum_{j=1}^{i-1}\text{gcd}(i,j)}$,这个问题明显好求一些。 如果强行枚举$i,j$肯定是要超时的,所以我们改变思路枚举最大公约数的值,设为$k$。 注意到当且仅当$(a,b)=1$时会有$(ak,bk)=k$,所以对于每一个$k$,设$a,b$中较大的一个数为$a$,首先$a$必须满足$ak\leq n$,即$a\leq \lfloor \dfrac{n}{k}\rfloor$。 我们固定住$a$的值,由于$b<a$,所以此时$b$有$\varphi(a)$种选择,所以对于一个固定的$a$与$k$,对答案的贡献为$\varphi(a)\times k$。 注意到这里有一种特殊情况,由于在原式中$i$与$j$是不相等的,所以当$a=1$时无解。 所以对于每一个固定的$k$,有$\displaystyle{\sum_{i=2}^{\lfloor n/k\rfloor}(\varphi(i)\times k)=k\sum_{i=2}^{\lfloor n/k\rfloor}\varphi(i)=k\sum_{i=1}^{\lfloor n/k\rfloor}\varphi(i)-k}$ 由于$k$有$1$到$n$共$n$种取法,所以最终答案为$\displaystyle{\sum_{k=1}^n\left(k\sum_{i=1}^{\lfloor n/k\rfloor}\varphi(i)-k\right)}$ 但同时我们也可以直接证明$\displaystyle{\sum_{k=1}^n\left(k\sum_{i=1}^{\lfloor n/k\rfloor}\varphi(i)-k\right)=\sum_{i=1}^n\sum_{j=1}^{i-1}\text{gcd}(i,j)}$,下证其正确性。 证明: $\displaystyle{\sum_{i=1}^n\sum_{j=1}^{i-1}\text{gcd}(i,j)=\sum_{i=1}^n\sum_{j=1}^{i}\text{gcd}(i,j)-\dfrac{n(1+n)}{2}}$ $\displaystyle{=\sum_{d=1}^n\left(d\sum_{i=1}^n\sum_{j=1}^{i}\left[\gcd(i,j)=d\right]\right)-\dfrac{n(1+n)}{2}}$ 注意到在这里$\gcd(i,j)=d$可以写成$\gcd(\dfrac{i}{d},\dfrac{j}{d})=1$ 所以原式$\displaystyle{=\sum_{d=1}^n\left(d\sum_{i=1}^{\lfloor n/d\rfloor}\sum_{j=1}^{i}\left[\gcd(i,j)=d\right]\right)-\dfrac{n(1+n)}{2}}$ $\displaystyle{=\sum_{d=1}^n\left(d\sum_{i=1}^{\lfloor n/d\rfloor}\varphi(i)\right)-\dfrac{n(1+n)}{2}}$ $\displaystyle{=\sum_{d=1}^n\left(d\sum_{i=1}^{\lfloor n/d\rfloor}\varphi(i)-d\right)}$ 证毕。 注意到$\displaystyle{k\sum_{i=1}^{\lfloor n/k\rfloor}\varphi(i)-k}$是可以先线性处理欧拉函数前缀和然后$\text O(1)$查询的,所以整个求和式可以在$\text{O}(n)$内做出来。 --- ```cpp #include <cstdio> #include <iostream> using namespace std; typedef long long ll; const int N = 4000005; ll n, cnt, vis[N], prime[N], phi[N]; int main() { // freopen("Uva11426.in", "r", stdin); // freopen("Uva11426.out", "w", stdout); ios::sync_with_stdio(false); // 预处理欧拉函数 phi[1] = 1; for (int i = 2; i <= N - 5; i ++) { if (!vis[i]) { prime[++ cnt] = i; phi[i] = i - 1; vis[i] = i; } for (int j = 1; j <= cnt; j ++) { if (prime[j] > vis[i] || prime[j] * i > N - 5) break; vis[i * prime[j]] = prime[j]; if (i % prime[j] != 0) phi[i * prime[j]] = phi[i] * (prime[j] - 1); else phi[i * prime[j]] = phi[i] * prime[j]; } } for (int i = 2; i <= N - 5; i ++) phi[i] += phi[i - 1]; while (true) { cin >> n; if (n == 0) return 0; long long ans = 0; for (int i = 1; i <= n; ++ i) ans += (phi[n / i] - 1) * i; cout << ans << endl; } return 0; } ```