主要思路
好您妈神仙啊。
考虑用 Lucas 把组合数分解：
\[ {n \choose m} = {n / k \choose m / k} {n \mod k \choose m \mod k} \]
好您妈神仙啊。
考虑用 Lucas 把组合数分解：
\[ {n \choose m} = {n / k \choose m / k} {n \mod k \choose m \mod k} \]
真就您🐎乱搞嘛。
我们可以考虑在怎样的一个情况下才能把一个数称之为\(x^k\)：自然是所有质因数的次数都为\(k\)的倍数，即\(b_i \equiv 0 \pmod k\)。那么，我们可以考虑把一个数分解，表示成质因数的幂：只不过这个次数要模个\(k\)。然后，进行哈希，放到unordered_map中。做哈希的时候做两份，一份是自身，还有一份是凑足完全\(k\)次方的哈希。
但是比较麻烦的是，如果我们搞所有质数，那么会超时。所以，这个时候要给所有质数标号，然后算出质数之间编号差来乘上其哈希幂。
蛮好想。考虑暴力，求完两者之间的\(\gcd\)之后枚举最大的因数即为答案。那么如何加速？我们发现\(gcd\)的最大因素也一定是\(a_1\)的因数之一，所以我们直接预处理\(a_i\)的因数，然后回答询问时直接\(\log n\)枚举即可。
今天被各路神仙吊打，顺利 gg。
在考场上我推了个有后效性的 DP，还以为是高斯消元，然后看到数据范围就 GG 了。这道题主要是把一些东西给转换掉了。
首先，对一个概率为\(p\)的事件，它的期望次数是\(\frac{1}{p}\)（参见这里）。然后，考虑一个状态\(dp[i]\)代表合成第\(i\)级武器的期望花费。显然\(dp[0] = a\)。
考虑\(dp[1]\)的求法，首先需要两个级别为\(0\)的武器，然后发现无论失败与否都可以保证至少又一个\(0\)级武器，所以我们只需要注意另外一个武器的花费就可以了：
\[ dp[1] = dp[0] + dp[1] \times \frac{1}{p} \]
今天这几题咋就那么毒瘤呢？
其实这道题考场上应该能做出来的，是一道很简单的计数问题。在考场上一看到字符串就懵了，不知道为什么我对字符串的字典序有阴影，现在看来就是一道傻逼题。
考虑这样计数：
首先我们在\(Q\)的剩余系内枚举数\(x_0\)，对于此每个数表示成\(x = (x_0 + k * P) \mod Q\)，思考一下发现这些数会随着\(k\)变化，且这些数会呈现周期性规律：也就是这些数在一个环上，我们可以考虑记录\(Q\)剩余系中每一个数在\(P\)中的贡献，记录成前缀和，计算答案时比较排名来判断环的方向（长弧或是短弧）。
具体看代码吧，细细品味一下应该就能理解了。