ブルーブリッジカップテーマ練習(サル分りんご)

アルゴリズムはVIPサルを訓練してリンゴを分けます
原題リンク:猿分リンゴ
テーマは秋になったことを説明して、n匹のサルはりんごをたくさん採って洞窟の中に置いて、翌日に平分することを約束しました.これらのサルは猿王孫悟空を崇拝しているので、りんごを残したいと思っています.最初のサルはこっそり洞窟に来て、りんごを平均n部に分けて、残りのm個のりんごを食べて、それから1部隠して、最後に残りのりんごを再び合わせました.これらのサルは順番に洞窟に来て、同じ操作をして、ちょうど毎回m個のリンゴが残っています.翌日、これらのサルは洞窟に来て、残りのりんごをn点に分けて、偶然にもm個残った.これらのサルは少なくともりんごを何個採ったのかと聞いた.
データ規模と約0考え:
この問題をする時、最初は複雑だったが、ネットで検索した後、李政道教授のサルの分桃算術問題に基づいて解くのは非常に効率的で、構想は以下の通りである.
リンゴの総数をxとし、総数に(n-1)m個のリンゴをy=x+(n-1)mとすることができ、このステップは毎回の残数mに(n-1)個を添加し、毎回サルが桃を分けた後に残数がないようにする.
1匹目のサルはm個のリンゴを食べて(x-m)(1/n)個隠し、すなわち1匹目のサルは(1/n)y個のリンゴを共有し、リンゴは((n-1)/n)yを残し、順次計算すると初日の最後のサルが分けた後に(n-1)n/nn)yが残っていると推定できる.
2日目は分配のみが必要なので、現在残っている桃の数を除いてサルの数は整数である.問題は少なくとも、平均分配数を1とすることができるからである.すなわち、(n−1)n/nn+1)y=1であり、この式を成立させるには、y=nn+1であり、y=x+(n−1)mに基づいてx=nn+1−(n−1)mを得ることができる.

#include
#include
#include
#include
using namespace std;
int  n, m;
long long sum;
int main()
{
	cin >> n >> m;
	sum = pow(n, n + 1) - (n - 1) * m;
	cout << sum;
	return 0;
}