CF1051B.Relatively Prime Pairs

入门

通过率:0%

时间限制:2.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

You are given a set of all integers from ll to rr inclusive, l<rl \lt r, (r−l+1)≤3⋅105(r - l + 1) \le 3 \cdot 10^5 and (r−l)(r - l) is always odd.

You want to split these numbers into exactly r−l+12\frac{r - l + 1}{2} pairs in such a way that for each pair (i,j)(i, j) the greatest common divisor of ii and jj is equal to 11. Each number should appear in exactly one of the pairs.

Print the resulting pairs or output that no solution exists. If there are multiple solutions, print any of them.

给你一个包含从 ll 到 rr(含)的所有整数的集合,其中 l<rl \lt r,(r−l+1)≤3⋅105(r - l + 1) \le 3 \cdot 10^5,且 (r−l)(r - l) 恒为奇数。

你需要将这些数恰好划分为 r−l+12\frac{r - l + 1}{2} 对,使得对每一对 (i,j)(i, j),ii 与 jj 的最大公约数(GCD)等于 11。每个数必须且仅出现在一对中。

请输出所得的配对结果;若无解,则输出表明无解的信息。若存在多种解法,输出任意一种即可。

输入格式

The only line contains two integers ll and rr (1≤l<r≤10181 \le l \lt r \le 10^{18}, r−l+1≤3⋅105r - l + 1 \le 3 \cdot 10^5, (r−l)(r - l) is odd).

唯一一行包含两个整数 ll 和 rr(1≤l<r≤10181 \le l \lt r \le 10^{18},r−l+1≤3⋅105r - l + 1 \le 3 \cdot 10^5,且 (r−l)(r - l) 为奇数)。

输出格式

If any solution exists, print "YES" in the first line. Each of the next r−l+12\frac{r - l + 1}{2} lines should contain some pair of integers. GCD of numbers in each pair should be equal to 11. All (r−l+1)(r - l + 1) numbers should be pairwise distinct and should have values from ll to rr inclusive.

If there are multiple solutions, print any of them.

If there exists no solution, print "NO".

如果存在解,则在第一行输出 "YES"。接下来的 r−l+12\frac{r - l + 1}{2} 行中,每行应包含一对整数。每对数的最大公约数(GCD)必须等于 11。所有 (r−l+1)(r - l + 1) 个数必须两两互不相同,且取值范围为 ll 到 rr(含端点)。

若存在多个解,输出任意一个即可。

若不存在解,则输出 "NO"。

输入输出样例

  • 输入#1

    1 8

    输出#1

    YES
    2 7
    4 1
    3 8
    6 5

输入解题思路,AI测评打分。不知道怎么写?

首页