最小的良好基础


难度级别
经常问 谷歌
二进制搜索 数学

问题陈述

假设我们给了所有的值一个整数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 的最大底数是 正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” 是字符串的长度。