2023-2024:teams:al_in_and_back_to_whk:24-nowcoder-3:g
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2023-2024:teams:al_in_and_back_to_whk:24-nowcoder-3:g [2024/07/24 13:27] 11231123 |
2023-2024:teams:al_in_and_back_to_whk:24-nowcoder-3:g [2024/07/24 13:28] (当前版本) 11231123 |
||
|---|---|---|---|
| 行 6: | 行 6: | ||
| 这里可能会遇到 $p=q$ 但是不是 $1$ 的情况。如果新的 $p,q$ 相等，那么我们对于原来的一定有 $(p+q)=2^k(p-q)$，进而就是 $q=\frac{2^k-1}{2^k+1}p$ ，于是我们只能令 $p=(2^k+1)*x$，然后新的数就是 $p=q=x$ ，然后这个x显然是不超过 $\frac{p}{3}$ 和 $q$ 的，所以相当于乘积除了一个 $3$ ，也至多只有 $log$ 次操作，变成 $x^2,1$ 继续处理即可。 | 这里可能会遇到 $p=q$ 但是不是 $1$ 的情况。如果新的 $p,q$ 相等，那么我们对于原来的一定有 $(p+q)=2^k(p-q)$，进而就是 $q=\frac{2^k-1}{2^k+1}p$ ，于是我们只能令 $p=(2^k+1)*x$，然后新的数就是 $p=q=x$ ，然后这个x显然是不超过 $\frac{p}{3}$ 和 $q$ 的，所以相当于乘积除了一个 $3$ ，也至多只有 $log$ 次操作，变成 $x^2,1$ 继续处理即可。 | ||
| + | |||
| + | ps：但是好像不加这个判断也能过，蛮怪的（ | ||
2023-2024/teams/al_in_and_back_to_whk/24-nowcoder-3/g.txt · 最后更改: 2024/07/24 13:28 由 11231123
