首页 > 试题广场 >

1=N

[编程题]1=N

热度指数：1792 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个正整数 ${X}$ ,令 ${X = 1}$ :
你可以对整数 ${X}$ 执行以下操作(次数不限):
选择一个大于等于 ${2}$ 的整数 ${K}$ 。支付 ${K}$ 单位的成本，令 ${X = K \times X}$ 。
给定正整数 ${N}$ ，找出使 ${X = N}$ 所需的最小成本

输入描述:

输入的第一行包含一个正整数。

输出描述:

输出使所需的最小成本

示例1

输入

输出

算法知识视频讲解

Java

BraveCoder

核心思路：将 N 分解为质因数的乘积，最小成本就是所有质因数（包括重复的）之和。

原因：当 a, b>=2 时，a+b<=a*b 恒成立，因此分解为质因数的成本最低。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        scanner.close();

        System.out.println(minCost(N));
    }

    private static int minCost(int n) {
        if (n == 1) return 0;

        int cost = 0;

        // 分解质因数
        for (int i = 2; i * i <= n; i++) {
            // 计算质因数i的指数
            while (n % i == 0) {
                cost += i;  // 累加质因数作为成本
                n /= i;
            }
        }

        // 如果剩余的n是一个质数
        if (n > 1) {
            cost += n;
        }

        return cost;
    }
}

发表于 2025-09-06 17:49:13 回复(0)

Java

一个普通求职者

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int n = in.nextInt();
        int cost = 0;
        for (int i = 2; n != 1; i++) {
            while (n != 1 && n % i == 0) {
                cost += i;
                n /= i;
            }
        }
        System.out.println(cost);
    }
}

发表于 2025-04-07 20:29:22 回复(0)

提交观点

问题信息

贪心数论

上传者：turnsoul

难度：

2条回答 7收藏 275浏览

1=N

输入描述:

输出描述:

输入

输出

问题信息

热门推荐

相关试题