1864c
CF1864C Divisor Chain
原题 翻译 好题难想 首先考虑\(x = 2^k\)怎么做,显然每次\(- 2^{k-1}\)即可 然后我们考虑对于\(x \neq 2^k\)怎么把他变成\(2^k\),答案就是\(x -= lowbit(x)\) 操作次数\(O(logn)\)的,\(< 1000\),正确性显然 ......
CF1864C 题解
# CF1864C Divisor Chain 题解 ## Links [洛谷](https://www.luogu.com.cn/problem/CF1864C) [Codeforce](https://codeforces.com/problemset/problem/1864/C) ## De ......
CF1864C Divisor Chain 题解
## 题意 给定一个整数 $x$,定义一个操作: > 选择一个 $x$ 的因数 $d$,把 $x$ 修改为 $x-d$。 限制相同的 $d$ 值不能选择超过 $2$ 次,需要在最多 $1000$ 次操作内把 $x$ 操作至 $1$,求操作序列。 ($1 \le x \le 10^9$)。 ## 题解 ......
CF1864C Divisor Chain
## 思路 刚拿到题,想了一些方法但都被推翻了,在这里列举出来,并给出反例: - 每次减去最小的因数,反例:$1024$ 等形如 $a^k$ 的数,每次都会减去 $a$ 导致 $a$ 的出现次数超过 $2$ 次。 - 每次减去大于等于 $\sqrt x$ 的因子,$x$ 为目前的数,并特判指数的情况 ......