题解
A
难度:黄
算法标签:数学、进制
题目翻译:给定进制 \(b\) 和分数 \(\frac{p}{q}\),求这个分数在 \(b\) 进制下是否是有限小数。
题目分析:
首先将分数化简(不用说了)。接下来有命题:若 \(/frac{1}{q}\) 为有限小数,则 \(/frac{p}{q}\) 必然为有限小数。且逆命题、否命题成立。证明略。
不难看出,若 \(b\) 包含 \(q\) 中的所有质因数,则该分数为有限小数,否则为循环小数。但暴力分解质因数的复杂度为 \(O(\sqrt{n})\) 无法通过这道题。因此考虑优化。这里可以使用 q /= GCD(p, b)
代替。
B
难度:蓝
算法标签:动态规划
题目翻译:
在一个长度为 \(m\) 的数组 \(b\) 中定义函数 \(f\):
例如:
\[\begin{aligned} f(1,2,4,8)& = f(1\oplus2,2\oplus4,4\oplus8) \\ &=f(3,6,12)\\&=f(3\oplus6,6\oplus12)\\&=f(5,10)\\&=f(5\oplus10)\\&=f(15)\\&=15 \end{aligned} \]现在,有一个长度为 \(n\) 的序列 \(a\),给了 \(q\) 组询问,请计算 \(a_l, a_{l+1}, \ldots, a_r\) 的所有连续子序列 \(\{b\}\) 中,\(f(b)\) 的最大值为多少。
题目分析:\(O(n^2)\) 预处理 \(f\) 每一层的值,然后递推,用 \(d[i][j]\) 表示以 \(i\) 为起点长度为 \(j\) 的最大值,然后 \(O(1)\) 查询。直接做就做完了。
C
难度:紫(未完)
标签:分数,frac,进制,983,Codeforces,题目,oplus,有限小数 From: https://www.cnblogs.com/chenaknoip/p/18536434