P13896 题解
Guizy
·
·
题解
显然不能枚举。
考虑质因数分解，丢到 vector 中。
```cpp
r(n)
{
int x = a[i];
for (int p = 2; p * p <= x; p++)
{
if (x % p == 0)
pri[p].push_back(i);
while (x % p == 0) x /= p;
if (x == 1) break;
}
if (x != 1) pri[x].push_back(i);
}
```
不难发现这样做之后 vector 中的数都是排好序的。
然后在做一遍，在 vector 中查询每个质因数的第二小下标即可。
为什么是第二小？
因为 $i$ 一定只会是一个质因数的第一小下标，$j$ 一定只会是一个质因数的第二小下标。
而 $i$ 就是现在枚举的，我们要求 $j$，所以就是第二小。
```cpp
r(n)
{
int x = a[i], mn = N;
for (int p = 2; p * p <= x; p++)
{
if (x % p == 0 && pri[p].size() > 1)
mn = min(mn, pri[p][1]);
while (x % p == 0) x /= p;
if (x == 1) break;
}
if (x != 1 && pri[x].size() > 1)
mn = min(mn, pri[x][1]); //vector 下标从 0 开始，所以第二小就是 pri[x][1]
if (mn != N)
return cout << i << " " << mn, 0;
}
```
注意 $j$ 是所有 $pri_{p, 1}$ 的 $\min$。并不是找到了直接输出就行。
hack 可以参考楼上大佬的：
```
5
6 15 10 3 5
```