小红的正整数构造

思路

题意很直白：给你一个区间 [L, R] 和一个正整数 k，在区间里找一个 k 的倍数。找不到就输出 -1。

那怎么快速判断区间里有没有 k 的倍数？换个角度想——大于等于 L 的最小的 k 的倍数是多少？ 如果这个数还在 R 以内，就是答案；否则就不存在。

怎么算"大于等于 L 的最小 k 倍数"？用向上取整除法：先算 ceil(L / k)，再乘回 k。整数写法就是 ((L + k - 1) / k) * k，这是一个非常经典的技巧。

举个例子：L=6, R=10, k=3。(6 + 3 - 1) / 3 = 8 / 3 = 2（整数除法），2 * 3 = 6。6 <= 10，输出 6。

再看：L=8, R=9, k=5。(8 + 5 - 1) / 5 = 12 / 5 = 2，2 * 5 = 10。10 > 9，输出 -1。

就这么简单，一行核心计算搞定。注意用 long long 防溢出就好。

代码

#include <iostream>
using namespace std;
int main() {
    long long L, R, k;
    cin >> L >> R >> k;
    long long x = ((L + k - 1) / k) * k;  // >= L 的最小 k 倍数
    cout << (x <= R ? x : -1) << endl;
    return 0;
}

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long L = sc.nextLong();
        long R = sc.nextLong();
        long k = sc.nextLong();
        long x = ((L + k - 1) / k) * k;  // >= L 的最小 k 倍数
        System.out.println(x <= R ? x : -1);
    }
}

L, R, k = map(int, input().split())
x = ((L + k - 1) // k) * k
print(x if x <= R else -1)

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line));
rl.on('close', () => {
    const [L, R, k] = lines[0].split(' ').map(Number);
    const x = Math.ceil(L / k) * k;
    console.log(x <= R ? x : -1);
});

复杂度分析

  • 时间复杂度: ，纯数学计算，没有任何循环。
  • 空间复杂度: ，只用了几个变量。

小结

这题的关键就一个点：向上取整除法。((a + b - 1) / b) * b 这个写法在算法题里用得非常多，比如求大于等于某个数的最小倍数、把数组按块分组等等场景都会碰到，属于基本功，记住就好。