CF1988A#

题意简述#

给定一个正整数 $n$ ，每次可以将其拆分成 $k$ 个数，求将 $n$ 变为 $n$ 个 $1$ 的最少操作次数。

题目分析#

对于一个数 $n$ ，我们每次可以将其拆分为 $(k-1)$ 个 $1$ ，和 $1$ 个 $(n-k)$ ，所以只需要暴力枚举 $n$ 能被拆分几次，就可以得出答案，具体见下：

当 $n=5,k=2$ 时：

$5$
$1,4$
$1,1,3$
$1,1,1,2$
$1,1,1,1,1$

不难发现只需要每次将 $n$ 减去 $k-1$ ，一直减到 $n<=1$ ，此时的操作次数即为答案。

Code#

1
#pragma GCC optimize(1, 2, 3, "Ofast", "inline")
2
#include <bits/stdc++.h>
3
using namespace std;
4
#define ll long long
5
#define int ll
6
#define ONLINE_JUDGE
7
#define MULTI_CASES
8
const int MaxN = 2e5+100;
9
const int INF = 1e9;
10
int T=1, N, M;
11
int a[MaxN];
12
int ans=0;
13
inline void Solve()
14
{
15
  cin>>N>>M;
16
  if(N==1){
17
    cout<<0<<endl;
18
    return ;
19
  }
20
  ans=0;
21
  for(int i=1;;i++){
22
    N-=M-1;
23
//    cout<<N<<endl;
24
    ans++;
25
    if(N<=1){
26
      break;
27
    }
28
  }
29
  cout<<ans<<endl;
30
}
31
signed main()
32
{
33
#ifndef ONLINE_JUDGE
34
  freopen(".in", "r", stdin);
35
  freopen(".out", "w", stdout);
36
#endif
37
  ios::sync_with_stdio(0);
38
  cin.tie(0),cout.tie(0);
39

40
#ifdef MULTI_CASES
41
  cin >> T;
42
  while (T--)
43
#endif
44
    Solve();
45
  //fclose(stdin);
46
  //fclose(stdout);
47
  return 0;
48
}