最小的良好基礎


難度級別
經常問 谷歌
二元搜尋 數學

問題陳述

假設我們給了所有的值一個整數n n個基數 當良好的基數k> = 1時為2。 假設我們給了 格式編號“ n”。 問題陳述要求找出n的最小良好底數並將其返回 格式。

最小的良好基礎

String n = “15”
2

說明:用Base 15編寫時的2是1111。

String n = “20”
19

說明:用Base 20編寫時的19是11。

最小良好基礎問題的算法

1. Set y to n-1.
2. Add the n-1 into the List.
3. From the i=2 to i< 63,
  1. Find out the val = pow of (y, 1.0 / i).
  2. From j=0 to j > - 3 and val + j > 1.
    1. Set d = val + j.
    2. And check if n % d is equal to 0.
      1. Find out this polynomial 1 + d + d ^ 2 + d ^ 3 + ... + d ^ i for d and up the current value of I and store into the sum.
    3. Check if this polynomial’s sum is equal to the n.
      1. Then add the value of d to the list.
4. Repeat the third process until the loop finishes.
5. Get the last element of the list and return that value.

解釋

給定數字n 格式。 每個數字 n 的最大底數是 n-1。 由於該值可以從3更改為10 ^ 18,因此最多可以容納64位數字。 最小的底數可以是2,最高可達63。對於任何n值,我們可以計算的最大底數是n-1,最小的底數是2。

因此,我們需要減少基數,以找到每一個中最極端的寫照。 對於每個編號的數字,我們將嘗試查找是否存在一個與尊敬等價的底數。 給定值= m,這個問題是找到滿足的整數d和n,

m = 1 + d + d ^ 2 + d ^ 3 +…+ d ^ i。

“ i”是每次我們遍歷數組時都可以更改的值(目標是將b最小化)。

根據等式,我們總是有一對答案,因此d1 = m-1。 因此,我們將匯總插入列表中的答案的可能值。 值(d1,…,dn)在列表中,我們將獲取最後一個值。 我們需要找到1 + b + b ^ 2 + b ^ 3 +…+ b ^基的多項式。

我們將跟踪一個函數,從中我們將找到每個可能數字的值。 我們採用的循環最多為62位,因為該數字最多可以由64位數字構成,但是採用63位可能會導致溢出。 我們將繼續進行此操作,直到找到最小值為止,同時還將其添加到列表中。 因此,我們只需要找到最小的鹼基並獲取最後一個鹼基即可。

推薦碼

C ++代碼尋找最小的良好基礎

#include<iostream>
#include<string>
#include<vector>
#include<math.h>

using namespace std;

long getGetPolynomial(long, int);
string getMinGoodBase(string n)
{
    long x = stoi(n);
    vector<long> listt;
    listt.push_back(x-1);
    long y = x-1;
    for (int i = 2; i < 63; i++)
    {
        double val = pow(y, 1.0 / i);
        long value = (long) val;
        for (int j = 0; j > -3 && value + j > 1; j--)
        {
            long d = value + j;
            if (y % d == 0)
            {
                long poly = getGetPolynomial(d, i);

                if (poly == x)
                {
                    listt.push_back(d);
                }
            }
        }
    }
    long end = listt[listt.size() - 1];
    string out = to_string(end);
    return out;
}
long getGetPolynomial(long d, int n)
{
    long out = 1;
    long k = 1;
    for (int i = 0; i < n; i++)
    {
        k *= d;
        out += k;
    }
    return out;
}
int main()
{
    string num="15";
    cout<<getMinGoodBase(num);
}
2

Java代碼找到最小的良好基礎

import java.util.ArrayList;
import java.util.List;

class GoodBase
{
    public static String getMinGoodBase(String n)
    {
        long x = Long.parseLong(n);
        List<Long> listt = new ArrayList<>();
        listt.add(x-1);
        long y = x-1;
        for (int i = 2; i < 63; i++)
        {
            double val = Math.pow(y, 1.0 / i);
            long value = (long) val;
            for (int j = 0; j > -3 && value + j > 1; j--)
            {
                long d = value + j;
                if (y % d == 0)
                {
                    long poly = getPolynomial(d, i);

                    if (poly == x)
                    {
                        listt.add(d);
                    }
                }
            }
        }
        long end = listt.get(listt.size() - 1);
        return end+"";
    }
    public static long getPolynomial(long d, int n)
    {
        long out = 1;
        long k = 1;
        for (int i = 0; i < n; i++)
        {
            k *= d;
            out += k;
        }
        return out;
    }
    public static void main(String args[])
    {
        String num="15";
        System.out.println(getMinGoodBase(num));
    }
}
2

複雜度分析

時間複雜度

2哪裡 “ n” 是字符串的長度。

空間複雜度

O(N) 哪裡 “ n” 是字符串的長度。