我们可以考虑在怎样的一个情况下才能把一个数称之为\(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\)级武器,所以我们只需要注意另外一个武器的花费就可以了:
 今天这几题咋就那么毒瘤呢?
 其实这道题考场上应该能做出来的,是一道很简单的计数问题.在考场上一看到字符串就懵了,不知道为什么我对字符串的字典序有阴影,现在看来就是一道傻逼题.
 具体看代码吧,细细品味一下应该就能理解了.
 这道题是一道裸题,考察莫比乌斯反演和 Dirichlet 卷积的知识.
 在这里我们规定\(n<m\),这两者调换不会对答案产生影响.然后我们来观察这个计数规律,发现每一个点对答案的贡献至少为\(1\),附加的贡献其实就是当前线段上除了本身的整点(整数坐标点)个数的两倍,换句话说就是: