题解 | #小红的正整数构造#

题目链接

题目描述

给定一个闭区间 $[l, r]$ 以及一个正整数 $x$ 。请在区间内找到一个整数 $k$ ，满足 $k$ 是 $x$ 的倍数，即 $k \pmod x = 0$ 。若存在多个满足条件的 $k$ ，输出任意一个；若不存在，输出 $-1$ 。

解题思路

题目的目标是在给定的闭区间 $[l, r]$ 中寻找一个 $x$ 的倍数。

一个简单直接的方法是遍历从 $l$ 到 $r$ 的所有整数，逐一检查它们是否是 $x$ 的倍数。但当区间 $[l, r]$ 很大时，这种方法效率会很低。

一个更高效的数学方法是：

首先，找到不小于 $l$ 的最小的 $x$ 的倍数。我们称这个数为 first_multiple。
- 如果 $l$ 本身就是 $x$ 的倍数（即 $l \pmod x = 0$ ），那么 first_multiple 就是 $l$ 。
- 如果 $l$ 不是 $x$ 的倍数，那么 first_multiple 就是比 $l$ 大的第一个 $x$ 的倍数。我们可以通过整数除法计算得出：first_multiple = (l / x + 1) * x。
然后，我们检查这个 first_multiple 是否在区间 $[l, r]$ 内。
- 由于我们的计算方式保证了 first_multiple >= l，我们只需要判断 first_multiple <= r 是否成立。
- 如果成立，那么 first_multiple 就是一个符合条件的答案。
- 如果不成立，说明不小于 $l$ 的最小的 $x$ 的倍数都已经超出了区间的右边界 $r$ 。因此，在区间 $[l, r]$ 内不存在 $x$ 的倍数，答案为 $-1$ 。

这种方法只涉及几次算术运算，与区间 $[l, r]$ 的大小无关，因此非常高效。

代码

c++
java
python

#include <iostream>

using namespace std;

int main() {
    long long l, r, x;
    cin >> l >> r >> x;

    // 计算不小于l的第一个x的倍数
    long long first_multiple;
    if (l % x == 0) {
        first_multiple = l;
    } else {
        first_multiple = (l / x + 1) * x;
    }

    // 检查这个倍数是否在区间[l, r]内
    if (first_multiple <= r) {
        cout << first_multiple << '\n';
    } else {
        cout << -1 << '\n';
    }

    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 x = sc.nextLong();

        // 计算不小于l的第一个x的倍数
        long first_multiple;
        if (l % x == 0) {
            first_multiple = l;
        } else {
            first_multiple = (l / x + 1) * x;
        }

        // 检查这个倍数是否在区间[l, r]内
        if (first_multiple <= r) {
            System.out.println(first_multiple);
        } else {
            System.out.println(-1);
        }
    }
}

# 读取l, r, x
l, r, x = map(int, input().split())

# 计算不小于l的第一个x的倍数
if l % x == 0:
    first_multiple = l
else:
    first_multiple = (l // x + 1) * x

# 检查这个倍数是否在区间[l, r]内
if first_multiple <= r:
    print(first_multiple)
else:
    print(-1)

算法及复杂度

算法：数学计算。
时间复杂度：该解法只包含几次算术运算，与输入数值的大小无关（在计算机整数表示范围内），因此时间复杂度为 $O(1)$ 。
空间复杂度：只使用了有限的几个变量来存储输入和中间结果，因此空间复杂度为 $O(1)$ 。