Найменшая добрая база


Узровень складанасці Жорсткі
Часта пытаюцца ў Google
Двайковы пошук Матэматыка Радок

Пастаноўка праблемы

Дапусцім, мы далі цэлае лік n для ўсіх значэнняў n аснова k роўныя 1, калі добрая аснова k> = 2. Дапусцім, мы далі радок нумар фармату 'n'. Пастаноўка праблемы просіць высветліць найменшую добрую базу n і вярнуць яе ў радок Фармат.

Прыклад

Найменшая добрая база

String n = “15”
2

Тлумачэнне: 15, калі напісана ў базе 2, гэта 1111.

String n = “20”
19

Тлумачэнне: 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-1 для любога значэння n, а мінімальная - 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дзе "П" - даўжыня радка.

Касмічная складанасць

Аб (п) дзе "П" - даўжыня радка.