# 最小的良好基礎

## 例

`String n = “15”`
```2
```

`String n = “20”`
`19`

## 最小良好基礎問題的算法

```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.```

### 解釋

m = 1 + d + d ^ 2 + d ^ 3 +…+ d ^ i。

“ i”是每次我們遍歷數組時都可以更改的值（目標是將b最小化）。

## 推薦碼

### 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<>();
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)
{
}
}
}
}
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” 是字符串的長度。