数学中的海盗游戏 - 用C#解决它

Question

我试图解决以下问题:

一些海盗胸前充满了宝藏(金币)

现在已经很晚了,所以他们决定早上把它分开

但是,其中一名海盗在半夜醒来时担心其他海盗会偷走他的份额,所以他决定自己分割宝藏.

他把它分成相等的份额(每个海盗一个).剩下一枚硬币,他扔到了船外.他拿走了他的份额,将其他股票放回胸前,然后回到他的小屋.

另一个海盗醒来并做同样的事情.是的,还有一个额外的硬币.是的,他将那枚硬币扔到了船上.

......每个海盗在夜间做一次(是的,有一个额外的硬币,他们每次都扔掉它),第二天早上他们醒来并将宝藏分成相等的份额.还剩下一个他们扔到船外.他们每个人都从事自己的分享,过着幸福的生活.

鉴于海盗的数量,最初可能在宝箱中的最小硬币数量是多少？

我尝试了下面这个,但任何大于8的数字都会让它瘫痪:

class Program
    {
        static long _input;
        static long _timesDivided;
        static string _output;

        static void Main()
        {
            Console.WriteLine("Enter the number of Pirates: ");

            var isValidInput = long.TryParse(Console.ReadLine(), out _input);

            if (!isValidInput)
            {
                Console.WriteLine("Please enter a valid number");
                Console.ReadKey();
                return;
            }

            Console.WriteLine("Caculating minimum treasure...\r\n \r\n");

            _timesDivided = _input + 1;

            var answer = CalculateTreasure();

            if (answer > 0)
                _output = string.Format("The minimum treasure is {0}", answer);
            else
                _output = "There was an error, please try another number";

            Console.WriteLine(_output);
            Console.ReadKey();
        }

        private static long CalculateTreasure()
        {
            long result = 0;

            try
            {
                while (true)
                {
                    result++;

                    while (true)
                    {
                        if (result % _input == 1)
                        {
                            break;
                        }
                        else
                        {
                            result++;
                        }
                    }

                    long treasure = result;

                    for (long i = 0; i < _timesDivided; i++)
                    {
                        var remainder = treasure % _input;

                        if (remainder != 1)
                        {
                            break;
                        }

                        var share = (treasure - remainder) / _input;

                        if (i == (_timesDivided - 1))
                        {
                            treasure = (treasure - (share * _input));

                            if (treasure == 1)
                                return result;
                        }
                        else
                        {
                            treasure = (treasure - share) - 1;
                        }
                    }
                }
            }
            catch (Exception ex)
            {
                //log exception here
                return 0;
            }
        }
    }

我相当肯定每个数字都必须是一个素数,所以我也考虑到了这一点.但是,我还没有找到解决这个问题的有效方法.我的数学太弱了

编辑

感谢上面提到的视频Fr3d,我现在有了我的CalculateTreasure方法:

private static long CalculateTreasure()
        {
            try
            {
                long result = (long)Math.Pow((double)_input, (double)_timesDivided);

                while (true)
                {
                    result--;

                    while (true)
                    {
                        if (result % _input == 1)
                        {
                            break;
                        }
                        else
                        {
                            result--;
                        }
                    }

                    long treasure = result;

                    for (long i = 0; i < _timesDivided; i++)
                    {
                        var remainder = treasure % _input;

                        if (remainder != 1)
                        {
                            break;
                        }

                        var share = (treasure - remainder) / _input;

                        if (i == (_timesDivided - 1))
                        {
                            treasure = (treasure - (share * _input));

                            if (treasure == 1)
                                return result;
                        }
                        else
                        {
                            treasure = (treasure - share) - 1;
                        }
                    }
                }
            }
            catch (Exception ex)
            {
                //log exception here
                return 0;
            }
        }

它有很大改进,但仍然不是100%最佳

Answer 1

我想我找到了正确的公式：

using System;
using System.Numerics;

namespace PirateCoins
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            Console.WriteLine(GetTreasure(n));
        }
        static BigInteger GetTreasure(int n)
        {
            BigInteger result = BigInteger.Pow(n, n + 1) - (n - 1);
            return result;
        }
    }
}

这是基于给出的序列 2 -> 7, 3 -> 79, 4 -> 1021, 5 -> 15621 。