2 条题解
-
0
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) 中间可能有的地方敲错了但是思路是对的 可以参考
-
-
0
因为看错题忘了每次还要藏一份导致一直0，比较崩溃（ 反应过来已经晚了 重新敲一遍只花了五六分钟(再也不敢眼瞎了
#include<bits/stdc++.h> using namespace std; int main() { int n,m,t,p,ans; cin>>n>>m; for(int i=n+m;;i+=n) { t=i; for(int j=1;j<=n;j++) { t=t-t/n-m; if(t%n==m) { p=0; } else if(t%n!=m) { p=1; break; } } if(p==0) { ans=i; break; } } cout<<ans; return 0; }
Guest
- 1
信息
- ID
- 799
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 9
- 标签
- (无)
- 递交数
- 24
- 已通过
- 4
- 上传者
-
teacher (1001)
