首先来一波正常套路，把枚举项变成\(\gcd\)。
\[ \begin{aligned} \prod_{i = 1}^n \prod_{j = 1}^n \frac{lcm(i, j)}{gcd(i, j)} &= \prod_{i = 1}^n \prod_{j = 1}^n \frac{ij}{gcd(i, j)^2} \\ &= \prod_{d = 1}^n d^{\sum_{i = 1}^n \sum_{j = 1}^n [\gcd(i, j) = d]} \end{aligned} \]
这套题全都是暴力出奇迹系列。
我们枚举一个端点，然后判断以这个点为右端点是否能计入答案。我们把序列做个前缀和\(prefix[]\)，然后发现计入答案的条件当且仅当\(prefix[i – n]\)小于等于\([i – n + 1, i]\)的最小值。这样可以保证所有的前缀都能为非负数。
然后用 sb 线段树搞下就行了，太特么傻逼了。
省选级别以上的 OI 赛事中的数学题，相比于 NOIp 的数学题来说要难很多。这篇文章我来记录学习了莫比乌斯反演和杜教筛之后的一些心得。以下是本文大纲：
给定一个\(n\)，求\(\sum_{i=1}^{n} \gcd(i,n)\)。
题意非常的小清新，然而推式子的时候很伤心。我一开始使用打表的方法，一直没成功发现其中的规律。所以推式子的能力还是相当重要的。
我们来分析一下。对于\(i\in [1,n], gcd(i,n)=1\)，它们对答案的贡献是\(\phi(n)\)。之后来看另一部分，也就是\(j\in [1,n], gcd(j,n)=k, k \neq 1\)，我们可以除下，变成\(k*gcd(\frac{j}{k},\frac{n}{k})=k, gcd(\frac{j}{k},\frac{n}{k})=1\)，其中根据欧拉定理，有\(\phi(k)\)个这样的\(gcd\)，所以推出得\(k*\phi(k)\)。答案最后只需统计\(k\)的因数乘上\(\phi(因数)\)即可。
最后可以考虑使用 map 记录已计算过的欧拉值，可获得常数优化。
// POJ2480.cpp
#include <cstdio>
#include <iostream>
#include <vector>
#include <map>
#define ll long long
using namespace std;
map<ll, ll> prefix;
vector<ll> getFracted(ll x)
{
vector<ll> res;
for (ll i = 1; i * i <= x; i++)
if (x % i == 0)
{
res.push_back(i);
if (i != x / i)
res.push_back(x / i);
}
return res;
}
ll phi(ll x)
{
ll ans = x;
for (ll i = 2; i * i <= x; i++)
if (x % i == 0)
{
ans -= ans / i;
while (x % i == 0)
x /= i;
}
if (x > 1)
ans -= ans / x;
return ans;
}
int main()
{
ll n;
while (scanf("%lld", &n) != EOF)
{
ll ans = 0;
vector<ll> container = getFracted(n);
ll siz = container.size();
for (int i = 0; i < siz; i++)
{
if (!prefix.count(n / container[i]))
prefix[n / container[i]] = phi(n / container[i]);
ll e = prefix[n / container[i]];
ans += e * container[i];
}
printf("%lld\n", ans);
}
return 0;
}
乍一看其实可以跟欧拉函数扯上关系。我们要求的是\(gcd(x,y) \in Prime, x, y \leq N\)的有序对个数。我们设那个质数为\(s\)，则可以化为：
\[ x = sa, y = sb \\ gcd(a, b) = 1 \]
嗯，看到欧拉函数的影子了。对于每一个质数\(s\)，它对答案的贡献是：
\[ 2 * \sum_{ 1 \leq i \leq \lfloor \frac{n}{s} \rfloor } \phi(i) – 1 \]
我来解释一下：因为\(x,y \leq n\)，所以\(sa \leq n\)，\(sb \leq n\)，得：
\[ a,b \leq \frac{n}{s} \]
所以会有这么多对，考虑这个是有序对，所以乘上二，再删除掉\((i,i)\)这样的有序对重复即可得到答案。注意，可以用前缀和欧拉函数值来进行优化。
// BZ2818.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX_N = 10000005;
ll n, phi[MAX_N];
bool isPrime[MAX_N];
int main()
{
//memset(isPrime, true, sizeof(isPrime));
scanf("%lld", &n);
for (int i = 2; i <= n; i++)
phi[i] = i;
for (int i = 2; i <= n; i++)
if (!isPrime[i])
for (int j = i; j <= n; j += i)
{
if (j != i)
isPrime[j] = true;
phi[j] = phi[j] / i * (i - 1);
}
phi[1] = 1;
for (int i = 2; i <= n; i++)
phi[i] += phi[i - 1];
long long ans = 0;
for (int i = 2; i <= n; i++)
if (!isPrime[i])
ans += 2 * phi[n / i] - 1;
printf("%lld", ans);
return 0;
}