参考：
https://matiji.net/exam/brushquestion/365/3846/4C6668FEB8CFD6520DE73B365B31D1A4
https://www.zhihu.com/question/50757823

问题引入

定义函数 f(x):x\bm{f(x)}:x 的因数个数。

f(1)=1,f(6)=4(6 的因数：1,2,3,6)f(1) = 1,f(6) = 4 \tag{$6$ 的因数：$1,2,3,6$}

现在给定一个数 nn ,找到最小数字 xx 满足 f(x)=nf(x) = n。如果 x>1000x > 1000，则输出 −1-1 。


输入格式：
一行包含一个整数 n
输出格式:
输出一个整数 x



输入:
4
输出：
6



备注：
其中 1 ≤\leq n ≤\leq 100


问题分析

我的算法比较朴素哈。因为题目限定了 nn 和 xx 的范围，而且比较小，所以我就试着用了一下暴力循环的方法。

首先还是介绍一下本文的重点，找一个数的因数的个数。这是从知乎上看到的比较好的一个思想，也运用了排列组合的知识。

方法是：
先把这个数分解成质数幂次相乘的形式，然后把各个质因数的幂次加一再做相乘得到。

举个例子，比如 24 。
按照分解成质数幂次相乘的形式， 24=23∗3124 = 2^3 *3^1 ，那么24的因数个数就是 (3+1)∗(1+1)=8(3+1)*(1+1)=8 个。

为什么把幂次加一相乘就是总的因数的个数呢？这是因为把一个数分解成质因数相乘的形式之后，它所有的因数信息就全包括在里面了，因为所有的因数都能分解成这些质数相乘的形式。

把幂次加一代表的是某个因数中包含这个质因数个数的情况。

24=23∗3124 = 2^3 *3^1 ，它某个因数中包含2的情况只有3+1=4种，0个2，1个2，2个2，3个2，而包含3的情况只有1+1=2种，则这个因数所有的可能情况为4*2=8种，这8种包括了所有因数的可能情况，并且互不相同（这个互不相同是由分解成的形式中都是质因数的幂次相乘保证的，由于质因数间互质，所以每种情况对应的因数必定是不同的）。

以上均为知乎大佬的解释。

题解代码

很意外暴力循环可以ac。可能是因为准备了个质数表吧（其实质数表也是找的，可以用代码生成，但是有现成的就先用吧）。

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
32
33
34
35
36
37
38
39
40
41
#拆解a，获取以i为底的指数次项
def getDivisor(a, i):
    ans = 0
    while a % i == 0:
        ans += 1
        a /= i
    return ans



primes = [
2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,
107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,
223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,
337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,
457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,
593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,
719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,
857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,
997]

n = int(input())
flag = 0 #判断x有没有超出上限
for i in range(1,1001):
    t = getDivisor(i, primes[0]) #t最终是因子的个数

    for j in primes:
        if j == 2:
            t = t+1
            continue
        if i >= j:
            t = t * (getDivisor(i,j)+1)
        else:
            break
    if t == n:
        flag = 1
        print(i)
        break

if flag == 0:
    print(-1)

OvO