Pirate trò chơi môn Toán - Giải quyết nó với C#

Question

Tôi cố gắng để giải quyết vấn đề sau:

Một số tên cướp biển có một ngực đầy kho báu (tiền vàng)

Nó là muộn vào buổi tối, Vì vậy, họ quyết định chia nó ra vào buổi sáng

Nhưng, một trong những tên cướp biển thức dậy vào nửa đêm lo ngại rằng những tên cướp biển khác sẽ ăn cắp phần của anh ấy.

Anh ấy chia thành chia sẻ bằng nhau (một cho mỗi tên cướp biển). Còn lại đồng xu mà anh ta ném xuống biển. Anh lấy phần của mình, đặt các cổ phiếu khác vào ngực, và trở về cabin của mình.

Một tên cướp biển khác thức dậy và làm điều tương tự. Có, vẫn còn một đồng xu thêm. Vâng, anh ta ném tiền xu đó lên tàu.

... Mỗi tên cướp biển thực hiện điều này một lần trong đêm (có, có thêm đồng xu thêm và họ ném nó lên mỗi lần), và sáng hôm sau họ thức dậy và chia kho báu thành các phần bằng nhau. Có là một trong những trái mà họ ném overboard. Họ từng lấy số và sống hạnh phúc mãi mãi.

Với số lượng cướp biển, số tiền nhỏ nhất mà có thể có trong kho báu ban đầu là bao nhiêu?

Tôi đã thử các sau đây, nhưng bất kỳ số lượng lớn hơn 8 mang nó đến đầu gối của nó:

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; 
      } 
     } 
    } 

Tôi khá chắc chắn rằng tất cả các số phải là số nguyên tố, vì vậy tôi cũng đã cố gắng trên với ý nghĩ đó. Tuy nhiên, tôi đã không thể tìm ra một công thức hiệu quả để giải quyết vấn đề này. toán học của tôi chỉ đơn giản là quá yếu

EDIT

Nhờ video Fr3d nói, bây giờ tôi có điều này cho phương pháp CalculateTreasure tôi:

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; 
      } 
     } 

Nó được cải thiện nhiều, nhưng vẫn không phải là 100% tối ưu

Answer 1

tôi nghĩ rằng tôi đã tìm thấy công thức đúng:

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; 
     } 
    } 
} 

này được dựa trên một chuỗi được đưa ra 2 -> 7, 3 -> 79, 4 -> 1021, 5 -> 15621.