题解 CF1451A 【Subtract or Divide】

简单题，我们打表找规律。 一个暴力程序 ``` #include <iostream> #include <cstdio> #include <cmath> #include <algorithm> #include <cstring> #include <cstdlib> #include <queue> #define FOR(i , b , e) for(int i = b; i <= e; i++) using namespace std; const int N = 1e6; int t; int dp[N]; int dfs(int k) { if(k == 1)return 0; if(dp[k])return dp[k]; int ee = 0x7ffffff , s = sqrt(k); for(int i = 2; i <= s; i++) { if(k % i == 0)ee = min(ee , min(dfs(i) , dfs(k / i))); } return min(ee , dfs(k - 1)) + 1; } void work() {/* int n;scanf("%d" , &n); printf("%d\n" , dfs(n));*/ FOR(i , 1 , 50)printf("%d\t" , i) ,printf("%d\t" , dfs(i)),puts(""); } int main() { scanf("%d" , &t); FOR(i , 1 , t)work(); return 0; } ``` 得到 [表](https://www.luogu.com.cn/paste/xy1or48s) 不难发现在 4 ~ 50 中奇数是 3 ，偶数是 2。但是前面几位数不满足条件，我们大胆猜想结论就是这样(CF 的 A 题不会多难)交上去试试。 AC。 策略是这样： $$\begin{cases} n \rightarrow 2 \rightarrow 1 &\text{if }(2 \mid n)\\n \rightarrow n-1 \rightarrow 2 \rightarrow 1 &\text{if not}( 2 \mid n) \end{cases} $$