BGN73 构造数对

思路

这题看起来条件挺多，我们来逐个拆解。要找一对正整数 满足：

  2. （b 整除 a）

条件这么多，别慌，先想想有没有什么特殊构造能一把全满足。

关键观察：取 。

验证一下：

  • ✓
  • ✓（自己整除自己）
  • ，当 时成立 ✓
  • ，当 时成立 ✓

所以只要 ， 就是一组合法解。

那 呢？此时 和 都只能取 ，但 不满足 ，所以无解，输出 。

就是这么简单，构造题的核心就是找到一个巧妙的构造方式，不用暴力搜索。

代码

#include <iostream>
using namespace std;
int main() {
    long long x;
    cin >> x;
    if (x <= 1) {
        cout << -1 << endl;
    } else {
        cout << x << " " << x << endl;
    }
}

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long x = sc.nextLong();
        if (x <= 1) {
            System.out.println(-1);
        } else {
            System.out.println(x + " " + x);
        }
    }
}

x = int(input())
if x <= 1:
    print(-1)
else:
    print(x, x)

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
rl.on('line', (line) => {
    const x = BigInt(line.trim());
    if (x <= 1n) {
        console.log(-1);
    } else {
        console.log(`${x} ${x}`);
    }
    rl.close();
});

复杂度分析

  • 时间复杂度：，直接输出结果。
  • 空间复杂度：，只用了常数个变量。