「LOJ2328」「清华集训 2017」避难所

发表于 | 更新于 | 分类于 | 阅读次数：

题意简述

LOJ 2328

设 $F(n,b)$ 表示 $n$ 在 $b$ 进制下各个位上数字的乘积。
如果想求一个最小的 $n$，使得 $p=F(n,b)$，那么一种贪心的方法是从 $b-1$ 开始往下试，如果是 $n$ 的约数就把它放在此时最低的位上。
显然贪心是错的。例如 $b=9,p=216$，那么贪心会给出 $n=(3338)_9$，但正确答案是 $n=(666)_9$。
给定 $b$，你需要给出一个 hack 数据 $p$ 以及它的最优解，或说明不存在。要求 $p\le 10^{18}$。
$t$ 组数据，$t\le 200, 1\le b\le 100000$。

主要思路

打表发现 $b> 127$ 都有解。
一种构造方法是令 $p = x^3y^3$，其中 $xy < x^3 < b, y^2 \ge b$。此时贪心就会翻车。
枚举 $xy$，复杂度 $O(b)$。

不小于 $127$ 的，同样暴力打表，发现答案形式均可以是 $p = xy^2$ 的形式。
于是可以 $O(b^2)$ 出解。

有意思的一点是 $b \le 12$ 时仅有 $b = 9$ 有解。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
def check( x, n ):
    res = 0
    i = n - 1
    while i >= 2:
        while x % i == 0:
            x /= i
            res += 1
        i = min(x, i - 1)
    if res > 3: return True
    else: return False

def solve():
    n = int(input())
    if n <= 127:
        for i in range(n - 1, 0, -1):
            for j in range(n - 1, 0, -1):
                if check(i * j * j, n):
                    print (3, i, j, j)
                    return
    else:
        for i in range(n - 1, 0, -1):
            if check(i * i * i, n):
                print (3, i, i, i)
                return
    print (-1)
    return

case = int(input())
while case > 0:
    solve()
    case -= 1