P13896 题解

显然不能枚举。

考虑质因数分解，丢到 vector 中。

pri_i

表示能被

i

整除的数的下标。

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 可以参考楼上大佬的：

CPP

5
6 15 10 3 5

文章操作

相关推荐

评论

P13896 题解