LibreOJ#3144. 「APIO 2019」奇怪装置 – 题解

主要思路

自己推了三个假的循环,遂奔向题解。

先考虑设循环节为 \(k\),且考虑最终 \(x = 0, y = 0\) 的局势。我们考虑怎样的循环节才能迭代一次、得到同样的 \(x = 0, y = 0\) 的局势。不妨直接带入 \(k\):

\[ x = (k + \lfloor \frac{k}{B} \rfloor) \bmod A, y = k \bmod B \]

继续阅读LibreOJ#3144. 「APIO 2019」奇怪装置 – 题解

Codeforces 1247D:Power Products 题解

主要思路

真就您🐎乱搞嘛。

我们可以考虑在怎样的一个情况下才能把一个数称之为\(x^k\):自然是所有质因数的次数都为\(k\)的倍数,即\(b_i \equiv 0 \pmod k\)。那么,我们可以考虑把一个数分解,表示成质因数的幂:只不过这个次数要模个\(k\)。然后,进行哈希,放到unordered_map中。做哈希的时候做两份,一份是自身,还有一份是凑足完全\(k\)次方的哈希。

但是比较麻烦的是,如果我们搞所有质数,那么会超时。所以,这个时候要给所有质数标号,然后算出质数之间编号差来乘上其哈希幂。

继续阅读Codeforces 1247D:Power Products 题解

「Universal OJ Round #3」核聚变反应强度 – 题解

主要思路

蛮好想。考虑暴力,求完两者之间的\(\gcd\)之后枚举最大的因数即为答案。那么如何加速?我们发现\(gcd\)的最大因素也一定是\(a_1\)的因数之一,所以我们直接预处理\(a_i\)的因数,然后回答询问时直接\(\log n\)枚举即可。

继续阅读「Universal OJ Round #3」核聚变反应强度 – 题解