题解 - 猴子分苹果

0
Guest
- Guest
0
大青果皇帝*安排化*晓辉 (波尔多阶鸦) LV 9 @ 2024-12-15 11:15:51
诏曰
```
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,m;
	cin>>n>>m;
	long long ans=0;
    ans=pow(n,n+1)-(n-1)*m;
	cout<<ans;
	return 0;
}
```
- 大青果皇帝*安排化*晓辉 (波尔多阶鸦) @ 2024-12-15 11:16:40
  
  没那么麻烦
- 242000608 @ 2024-12-15 13:01:22
  
  做一点小小的补充首先这份题解比较令人吃惊因为时间复杂度仅为O(1), 原因也很简单，运用了数学的方法直接推导得到的，那他咋推的，这里我补充一点粗略的过程 First：《迭代》首先我们假设最终答案为k 根据题意，第一只猴子操作完剩余的苹果数应为 k1=[（k-m）(n-1)]/n 如此反复后第n次的结果应为 kn=[(k-m)(n-1)^n-mn(n-1)^（n-1）-...-m*n^(n-1)*n]/n^n
  
  很复杂对吧然后再进行一次分配即kn+1=（kn-m）/n 我们要保证kn+1是一个正整数即kn+1=[(k-m)(n-1)^n-mn(n-1)^（n-1）-...-m*n^(n-1)n-mn^n]/n^（n+1）是正整数利用一个公式 a^n-b^n=(a-b)(a^(n-1)+a^(n-2)*b+...+b^(n-1)) 对原式进行化简（可以想想怎么化简，这玩意太冗长了我就逃个懒）得：
  
  kn+1=[(k-m)(n-1)^n+m*(n-1)^n+mn^(n+1)+m(n-1)^(n+1)]/n^（n+1）我们发现m*n^(n+1)这个分子上的一项可以不用管（可整除分母），而剩余项化简可得：
  
  kn+1=[（k+m*n-m）(n-1)^n]/n^(n+1)
  
  而显然n-1和n互质所以只需让k+m*n-m能整除分母即可而这一项又不能为0
  
  所以kmin=n^（n+1)-m*(n-1) 中间可能有的地方敲错了但是思路是对的可以参考