算法训练（VIP）——猴子分苹果

题目描述

秋天到了，n 只猴子采摘了一大堆苹果放到山洞里，约定第二天平分。

这些猴子很崇拜猴王孙悟空，所以都想给他留一些苹果。

第一只猴子悄悄来到山洞，把苹果平均分成 n 份，把剩下的 m 个苹果吃了，然后藏起来一份，最后把剩下的苹果重新合在一起。

这些猴子依次悄悄来到山洞，都做同样的操作，恰好每次都剩下了 m 个苹果。

第二天，这些猴子来到山洞，把剩下的苹果分成 n 分，巧了，还是剩下了 m 个。

问原来这些猴子至少采了多少个苹果。

输入格式

两个整数 n，m

输出格式

一个整数，表示原来苹果的数目

样例输入

5 1

样例输出

15621

数据范围

0 < m < n < 9

题解一

DFS（会超时）：

猴子的数量达到 8 时，起始数量就破亿了

#include <iostream>
using namespace std;

int n, m;

int dfs(int u, int sum)
{
	if(sum % n != m) return 0;
	
	if(u == n) return 1;
	
	return dfs(u + 1, sum - sum / n - m);
}

int main()
{
	cin >> n >> m;
	
	for (int i = 1; i <= 200000000; i ++) 
		if(dfs(0, i))
		{
			cout << i << endl;
			return 0;
		}
}
           

题解二

推公式：

上世纪物理学家李政道给出的通解。神奇的是，如果不用 sum 存储结果，直接输出的话，会有 45% 的错误。

#include <iostream>
#include <cmath>  
using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;
    
    int sum = pow(n, n + 1) - (n - 1) * m;
    
    cout << sum << endl;
    return 0;
}