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

Question

我正在尝试解决以下问题:

Some pirates have a chest full of treasure (gold coins)

It is late in the evening, so they decide to split it up in the morning

But, one of the pirates wakes up in the middle of the night concerned that the other pirates will steal his share so he decides to go divide the treasure himself.

He divides it into equal shares (one for each pirate). There is one coin left over, which he throws overboard. He takes his share, puts the other shares back in the chest, and returns to his cabin.

Another pirate wakes up and does the same thing. Yes, there is still one extra coin. Yes, he throws that coin overboard.

... Each pirate does this once during the night (yes, there is an extra coin and they throw it overboard each time) , and the next morning they wake up and divide the treasure into equal shares. There is one left over which they throw overboard. They each take their share and live happily ever after.

Given the number of pirates, what is the smallest number of coins that could have been in the treasure chest originally?

我尝试了以下方法，但任何大于 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。