Хурдтарин пойгоҳи хуб


Сатҳи душворӣ мушкил
Аксар вақт пурсида мешавад Google
Ҷустуҷӯи бинарӣ Матем сатр

Изҳороти мушкилот

Фарз мекунем, ки мо барои тамоми арзишҳои бутуни n додаем n пойгоҳи к мебошанд 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, 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ки дар "Н" дарозии сатр аст.

Мураккабии фазо

Эй (н) ки дар "Н" дарозии сатр аст.