你听说过循环不变式吗？不妨来品鉴一下吧：WeLikeStudying 大佬的博客：循环不变式
而这篇文章，只是对大佬博客的小小注解，外加一点实际应用。
-
我们可以把循环不变式理解成一组条件。在每次循环中，我们保证这组条件均为真。而最后循环就可以得出我们想要的结果。
-
如果思考本质，这实际上可以一种数学归纳法。我们保证了循环任何时候都满足条件，只需要验证满足了这组条件就能求出答案。
-
满足的条件可以是显示在代码中的，也可以是隐藏起来的。
举个例子，斐波拉契数列中，我们创造两个变量 \(a,b\)，且保证：
\[a = fib(i), b = fib(i + 1) \]那么就可以求出答案。
- 我们可以发现，选择一组好实现的条件，是化繁为简的关键。
现在我们看到这道题：
-
首先这道题和 \(gcd\) 有关，再看到数据范围，这意味着我们的复杂度只要和每个数的倍数有关，就能通过此题。
-
最简单的条件是创造数组 \(f_i\)，且 \(f(i)=ans(i)\)。其中 \(ans(i)\) 就是 \(gcd(a,b,c,d) = i\) 的答案。但是我们发现这不好实现。
-
考虑扩大条件。我们不能求出恰好的答案，但是我们可以求出至少的答案。具体地，我们定义 \(g_i\) 为 \(gcd(a,b,c,d) | i\) 的个数。我们枚举每个数的倍数，可以在 \(n \ln n\) 的时间内求出来。
-
最后，我们寻找这两者的关系。要得到恰好为 \(i\) 的答案，就要把所有比 \(i\) 大的答案都从 \(g_i\) 剔除出去。因此，我们得出 \(f_i = g_i - \sum_{j | i} f_j\)。
-
注意这个式子去除了一次 \(f_i\)。但是由于此时 \(f_i\) 没有求出，应该为 \(0\)，所以没有影响。
总结一下，在程序中，我们只要满足下面的条件，那么 \(f(1)\) 就是答案（设 \(i\) 在序列中出现了 \(num_i\) 次）。
\[g_i = \sum_{j | i} num_j \]\[f_i = g_i - \sum_{j | i} f_j \]下面是代码：
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e4 + 5;
int n;
int a[N];
long long ton[N], f[N], g[N];
void solve() {
for (int i = 1; i <= n; ++i) cin >> a[i];
int mxa = 0;
for (int i = 1; i <= n; ++i) mxa = max(mxa, a[i]);
for (int i = 1; i <= mxa; ++i) f[i] = g[i] = ton[i] = 0;
for (int i = 1; i <= n; ++i) ++ton[a[i]];
for (int i = mxa; i >= 1; --i) {
long long sum_g = 0, sum_f = 0;
for (int j = 1; i * j <= mxa; ++j) {
sum_g += ton[i * j];
sum_f += f[i * j];
}
g[i] = (sum_g * (sum_g - 1) * (sum_g - 2) * (sum_g - 3)) / (4 * 3 * 2 * 1);
f[i] = max(1LL * 0, g[i] - sum_f);
}
cout << f[1] << endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
while (cin >> n) solve();
return 0;
}