题目链接

构造数对

题目描述

给定一个正整数 ，请你构造一个由两个正整数 组成的数对，使其同时满足下列全部条件：

  2. 整除 （）

若存在多个满足要求的数对，你可以输出其中任意一个；若不存在，则输出 -1。

解题思路

这是一个构造性问题，我们可以尝试寻找一个最简单的构造方案。 题目要求 和 都是不超过 的正整数，一个自然的想法是令 和 都取最大值，即 。我们来验证这个构造是否满足所有条件。

  1. ：当 时，此条件为 。因为题目保证 是正整数，所以 ，该条件恒成立。
  2. ：当 时，此条件为 ，即 能被 整除。对于任意正整数 ，该条件恒成立。
  3. ：当 时，此条件为 ，即 。这个不等式当且仅当 时成立。如果 ，则 不成立。
  4. ：当 时，此条件为 ，即 。这个不等式同样当且仅当 时成立。如果 ，则 不成立。

综上所述，当 时，数对 满足所有四个条件，是一个合法的解。 当 时，唯一可能的正整数对是 。我们已经验证过它不满足条件3和4，因此当 时无解。

最终的策略是：

  • 如果输入的 等于 ，则无解，输出 -1。
  • 如果输入的 大于 ，则构造 并输出。

代码

#include <iostream>

using namespace std;

int main() {
    int x;
    cin >> x;
    if (x == 1) {
        cout << -1 << endl;
    } else {
        cout << x << " " << x << endl;
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        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)

算法及复杂度

  • 算法：数学、构造
  • 时间复杂度：，程序只包含一次读入和一次判断输出。
  • 空间复杂度：，只使用了常数个变量。