ຖານທີ່ດີທີ່ນ້ອຍທີ່ສຸດ


ລະດັບຄວາມຫຍຸ້ງຍາກ Hard
ຖາມເລື້ອຍໆໃນ ກູໂກ
ການຄົ້ນຫາຖານສອງ ຄະນິດສາດ string

ຖະແຫຼງການບັນຫາ

ສົມມຸດວ່າພວກເຮົາໄດ້ເອົາເລກເຕັມ n, ສຳ ລັບຄ່າທັງ ໝົດ ຂອງ n ຖານ k ແມ່ນ 1 ເມື່ອຖານທີ່ດີ k> = 2. ສົມມຸດວ່າພວກເຮົາໄດ້ໃຫ້ string format-number 'n'. ຄຳ ຖະແຫຼງກ່ຽວກັບບັນຫາຂໍໃຫ້ຊອກຫາຖານທີ່ດີທີ່ນ້ອຍທີ່ສຸດຂອງ n ແລະສົ່ງຄືນມັນ string ຮູບແບບ.

ຍົກຕົວຢ່າງ

ຖານທີ່ດີທີ່ນ້ອຍທີ່ສຸດ

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 ໃນ string ຮູບແບບ. ທຸກໆຕົວເລກ 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ບ່ອນທີ່ "n" ແມ່ນຄວາມຍາວຂອງຊ່ອຍແນ່.

ຄວາມສັບສົນໃນອະວະກາດ

O (n) ບ່ອນທີ່ "n" ແມ່ນຄວາມຍາວຂອງຊ່ອຍແນ່.