ყველაზე პატარა კარგი ბაზა


Რთული ტური Hard
ხშირად ეკითხებიან 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-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

ჯავის კოდი, რომ იპოვოთ ყველაზე პატარა კარგი ბაზა

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სადაც "ნ" სიმების სიგრძეა.

სივრცის სირთულე

O (n) სადაც "ნ" სიმების სიგრძეა.