算法分析

题目求的是：对于任意的小于x的正整数 i，都有g(x)>g(i)，不超过N的最大x，等价于求约数之和最多的最小的数

可以知道，每一个数 $t$ 都可以通过用质因数 $t = 2^{c_1} × 3^{c_2} × 5^{c_3} × 7^{c_4}…$

• 1、假设每个质因子都只用一次，最多只用9个质因子，因为2 * 3 * 5 * 7 * ... * 23 = 223,092,870 < 2 * 10^9，而2 * 3 * 5 * 7 * ... * 23 * 29 = 6,469,693,230 > 2 * 10^29
• 2、每个质因子的次数最多是30，因为最小的质因子是2,2^30 = 1,073,741,824 < 2 * 10^9,2^31 > 2 * 10^9
• 3、所有质因子的次数一定递减，即c1 >= c2 >= c3 >=...，为了保证约数个数相同时，找到最小的那个，假设$t = 2^{c_1} × 3^{5} × 5^{4} × 7^{c_4}…$，$c_1 >= 5 >= 4 >= c_4$，交换3和5的次数即变成$t = 2^{c_1} × 3^{4} × 5^{5} × 7^{c_4}…$，这样交换约数个数相同，可$3^4 * 5^5$ > $3^5 * 5^4$，交换后该数变大了，因此质因子次数一定递减

通过爆搜，枚举每个因子用多少个，找出约数个数最多，最小的数

时间复杂度

不好分析

参考文献

算法提高课

Java 代码

import java.util.Scanner;

public class Main {
    static int n;
    static int[] primes = new int[] {2,3,5,7,11,13,17,19,23};
    static int maxv = 0,number = 0;
    //u表示枚举到当前质数位置，last表示最多可以枚举的个数，p表示当前的值，s表示约数个数
    static void dfs(int u,int last,int p,int s)
    {
        if(s > maxv || s == maxv && p < number)
        {
            maxv = s;
            number = p;
        }

        if(u == 9) return;

        for(int i = 1;i <= last;i ++)
        {
            if((long)p * primes[u] > n) break;
            p *= primes[u];
            dfs(u + 1,i,p,s * (i + 1));
        }
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        dfs(0,30,1,1);
        System.out.println(number);
    }
}