主要思路
蛮好想。考虑暴力，求完两者之间的\(\gcd\)之后枚举最大的因数即为答案。那么如何加速？我们发现\(gcd\)的最大因素也一定是\(a_1\)的因数之一，所以我们直接预处理\(a_i\)的因数，然后回答询问时直接\(\log n\)枚举即可。
蛮好想。考虑暴力，求完两者之间的\(\gcd\)之后枚举最大的因数即为答案。那么如何加速？我们发现\(gcd\)的最大因素也一定是\(a_1\)的因数之一，所以我们直接预处理\(a_i\)的因数，然后回答询问时直接\(\log n\)枚举即可。
这道题二次函数的暴力分有 60 分，正解来自于论文。
这道题的主要是利用了一个结论，并且运用了辗转相除法的一种思想来对问题进行化简。首先，我们把向量调整至同向，且使\(|\vec{a}| < |\vec{b}|\)，然后再来推导一个结论：
结论 对于\(\vec{a}, \vec{b}\)，如果\(<\vec{a}, \vec{b}> \geq \frac{\pi}{3}\)，那么答案就是\(min\{|\vec{a}|, |\vec{b}|\}\)。
这个结论的证明参见《欧几里得算法的应用》。所以，我们就可以大概知道，我们可以将较长的向量分解：\(\vec{b} = k\vec{a} + \vec{b’} \)。由于我们知道，这道题可以笑掉这个\(k \vec{a}\)，所以就可以用辗转相除法的套路进行处理。具体见代码：
今天这几题咋就那么毒瘤呢？
其实这道题考场上应该能做出来的，是一道很简单的计数问题。在考场上一看到字符串就懵了，不知道为什么我对字符串的字典序有阴影，现在看来就是一道傻逼题。
考虑这样计数：
这道题是一道很好的题，包含了数论里面的很多技巧。
首先，这是一道多组询问的题，询问数量非常的大，遂放弃使用欧拉函数来求。考虑可以使用莫比乌斯函数的性质来搞，开始从这方面分析。
复习一下莫比乌斯函数的定义：
\[ \mu(x) = \begin{cases} 0, 在x中存在指数大于一的质因子 \\ 1, 在x中质因子指数都为1且质因子个数为偶数 \\ -1, 在x中质因子质数都为1且质因子个数为奇数 \end{cases} \]
我们观察一下答案式子：\(\sum_{i,j} [gcd(x,y)=d]\)。我们先把\(gcd\)部分进行变换：
\[gcd(\frac{x}{d}, \frac{y}{d}) = 1\]
显然，这样的对数为\( \lfloor \frac{x}{d} \rfloor*\lfloor \frac{y}{d} \rfloor \)。我们考虑容斥：因为如果暴力累加的话，会多出很多不该存在的部分，比如说又是2的倍数又是3的倍数的部分。
所以最后答案式为：
\[\sum_{i=1}^{min\{a,b\}} \mu(i)*\lfloor \frac{x}{i} \rfloor*\lfloor \frac{y}{i} \rfloor \]
这时有个技巧，我们可以证明在整数段\([x, min\{ \lfloor \frac{a}{\lfloor \frac{a}{x} \rfloor} \rfloor, \lfloor \frac{b}{\lfloor \frac{b}{x} \rfloor} \rfloor \} ]\)上，\(\lfloor \frac{x}{i} \rfloor*\lfloor \frac{y}{i} \rfloor\)的结果是一样的，直接前缀和与之相乘即可。最后这样的段最坏情况为\(O(\sqrt{a}+\sqrt{b})\)，所以时间复杂度比较低。
// BZ1101.cpp
#include <bits/stdc++.h>
#define ll int
using namespace std;
const int MAX_N = 5e4 + 200;
ll mobi[MAX_N], sum[MAX_N], n;
bool vis[MAX_N];
int main()
{
for (int i = 1; i < MAX_N; i++)
mobi[i] = 1;
for (int i = 2; i < MAX_N; i++)
{
if (vis[i])
continue;
mobi[i] = -1;
for (int j = 2; i * j < MAX_N; j++)
{
vis[i * j] = true;
if (j % i == 0)
mobi[i * j] = 0;
else
mobi[i * j] *= -1;
}
}
for (int i = 1; i < MAX_N; i++)
sum[i] = sum[i - 1] + mobi[i];
scanf("%d", &n);
while (n--)
{
int a, b, k, gx;
scanf("%d%d%d", &a, &b, &k);
a /= k, b /= k;
int ans = 0;
for (int i = 1; i <= min(a, b); i = gx + 1)
{
gx = min(a / (a / i), b / (b / i));
ans += (sum[gx] - sum[i - 1]) * (a / i) * (b / i);
}
printf("%d\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;
}