神秘结论题，感觉不太符合当代 OI 风格。
题目链接
给定一列正整数 ，求区间乘积为完全平方数的区间个数，并输出前 个区间。
首先可以想到对每个数暴力质因数分解，使用 Pollard-Pho 算法，总复杂度 。
如果能做的话，可以给每个质数随机赋权，统计一下异或和为 的区间。
可惜出题人甚至不愿意放一个 的点。
注意到二次剩余（可以理解为模意义下完全平方数）这个东西。
直觉上讲，我们已知对于一个奇质数 ，模 意义下有 个数是二次剩余，而完全平方数在任何奇质数模数下总是二次剩余。
因此直觉上讲，对于一个非完全平方数，通过随机取质数再判定二次剩余的方法，我们只有 的概率会判断错误，因此取 个随机质数大概就可以保证正确。
这里可以先给出模奇质数二次剩余的判别法：
为奇质数时， 在模 意义下是二次剩余，当且仅当
略证
对于必要性，假设 ，根据 Fermat 小定理，有 ，进而 。
对于充分性，考虑模 的简化剩余系
对于每一个 ，可以求出 使得 。
若不存在 ，则 中所有数可以两两配对，即 ，与 Wilson 定理矛盾。
至于二次剩余存在 个，可以从 解释。
我不太想引入 Legendre 符号等内容，但发现后文不太好描述，因此这里给出定义，对于奇质数 ，有：
显然
仅仅从这个判定方式来看，明显 对于 是完全积性的，因此显然两个二次剩余或两个非二次剩余相乘是二次剩余；一个二次剩余和一个非二次剩余相乘是非二次剩余（只考虑 ）。
不妨维护每个数模 意义下 的值，压成一个二进制数，为 则记 ，为 则记 ，为 时该位无效，也记为 。
这样若一段区间的异或和为 ，则这一段区间的乘积被选择的所有质数均判定为完全平方数，可以认为找到了一个解。
这样的做法是 的，这里 为质数数量，根据前文分析，可以取 。
若 较小，可以筛法预处理全部二次剩余，遗憾的是这种做法可以被卡掉。
方法很显然，例如算法取前 个质数 ，则可以另取 个大质数 ，将它们判定结果计算出来，这可以看作 个 维向量，显然是线性相关的。
则一定可以取若干 ，使得 会被每一个 判定为完全平方数，但实际上只是若干互异质数的积。
若取前 小的质数，则构造复杂度是 的。
具体内容见 EI 的文章。
已经有人构造出了 以内质数的 Hack 数据。
文件不太大，我决定留个档。
洛谷选择加入 Hack 数据后开大时限，Loj 好像没加 Hack 也没开时限，不过卡一卡可以使用同一份代码在两边都过了。
还是 Loj 快，洛谷我是没跑进 1.5s 的，但是也卡成最优解了。
一个卡常技巧是我把对每个质数求 Euler 判定的过程展开了，fast_power 对每个质数生成特定版本的快速幂，每个质数都是编译期常数，取模可以特化；在洛谷上从 8s+ 干到 1s+；在 Loj 从 T 到 A。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
| #include <bits/stdc++.h>
using namespace std;
istream &operator>>(istream &is, __int128 &x) {
string s;
is >> s;
x = 0;
for (char c : s)
x = x * 10 + (c - '0');
return is;
}
template <uint32_t mod> uint64_t fast_power(uint64_t base) {
uint32_t power = (mod - 1) / 2;
uint64_t ret = 1;
for (; power; (base *= base) %= mod, power >>= 1)
if (power & 1)
(ret *= base) %= mod;
return ret;
}
uint64_t get_hash(__int128 s) {
uint64_t val = 0;
#define RUN_HASH(prime) \
val <<= 1, val |= fast_power<prime>(s % prime) != 1
RUN_HASH(1070951741U);
RUN_HASH(1170130207U);
RUN_HASH(1183971839U);
RUN_HASH(1245300233U);
RUN_HASH(1268569829U);
RUN_HASH(1298746283U);
RUN_HASH(1301668909U);
RUN_HASH(1302872999U);
RUN_HASH(1354681189U);
RUN_HASH(1375924369U);
RUN_HASH(1405604119U);
RUN_HASH(1563442729U);
RUN_HASH(1614890171U);
RUN_HASH(1668696331U);
RUN_HASH(1717435817U);
RUN_HASH(1849065671U);
RUN_HASH(1930615781U);
RUN_HASH(2056247341U);
RUN_HASH(2077402687U);
RUN_HASH(2167628587U);
RUN_HASH(2312421899U);
RUN_HASH(2439093781U);
RUN_HASH(2464088981U);
RUN_HASH(2530010933U);
RUN_HASH(2558376851U);
RUN_HASH(2664181133U);
RUN_HASH(2708760871U);
RUN_HASH(2825940619U);
RUN_HASH(2896962637U);
RUN_HASH(2955116233U);
RUN_HASH(3024086707U);
RUN_HASH(3111206317U);
RUN_HASH(3119513693U);
RUN_HASH(3137383213U);
RUN_HASH(3249720911U);
RUN_HASH(3413798779U);
RUN_HASH(3445601713U);
RUN_HASH(3450314113U);
RUN_HASH(3497939789U);
RUN_HASH(3502169413U);
#undef RUN_HASH
return val;
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
size_t n;
cin >> n;
vector<uint64_t> hash_val(n + 1);
for (size_t i = 1; i <= n; ++i) {
__int128 x;
cin >> x, hash_val[i] = get_hash(x);
}
for (size_t i = 1; i <= n; ++i)
hash_val[i] ^= hash_val[i - 1];
unordered_map<uint64_t, pair<size_t, vector<size_t>>> hash_map;
hash_map.reserve(n * 1.2);
for (size_t i = 0; i <= n; ++i)
hash_map[hash_val[i]].second.push_back(i);
size_t ans = 0;
for (const auto &[key, val] : hash_map)
ans += val.second.size() * (val.second.size() - 1) >> 1;
cout << ans << '\n';
size_t output_limit = 1e5;
for (size_t i = 0; i < n; ++i) {
auto &[st, vec] = hash_map[hash_val[i]];
for (size_t i = ++st; i < vec.size(); ++i) {
cout << vec[st - 1] + 1 << ' ' << vec[i] << '\n';
if (!--output_limit)
return 0;
}
}
return 0;
}
|
我不要求你的题总是开多倍时限，我不是恶魔。
但是，std 赛后被 Hack 叉掉是怎么回事？你的验题观念怎么了？18 岁可以给 CCF 供假的 std，36 岁开 不让人 Pollard-Pho，72 岁你就变成 74TrAkToR 了。
作为一名 OI 选手，我可能得喷死你，真的。