#1038. 陌生数对

陌生数对

题面描述:

我们称两个自然数 xxyy陌生数对,如果它们互不相同,并且不存在两个不同的且不为 11 的数 aabb,使得 xxyy 都可以被 aabb 整除。例如,6699 是陌生数对,因为唯一能同时整除它们的数是 33。但 12121818 不是,因为它们都能被 223366 整除。

给定一个自然数 xx 以及自然数 llrr,要求找到所有满足 lyrl \le y \le r 且能与 xx 组成陌生数对的数字 yy

输入:

在一行中输入三个正整数 x,l,rx, l, r

  • 1x1091 \le x \le 10^9
  • 1lr1091 \le l \le r \le 10^9
  • rl1000r - l \le 1000
输出:
  • 第一行输出一个数 kk,表示区间 [l,r][l, r] 中与 xx 不同的数的个数。
  • 第二行输出所有这些数,按从小到大的顺序排列。
样例输入1:
6 10 20
样例输出1:
9
10 11 13 14 15 16 17 19 20
提示:
测试点编号 限制
151-5 x100x \le 100, 1lr1001 \le l \le r \le 100
6106-10 x105x \le 10^5, l=rl = r
111511-15 x109x \le 10^9, l=rl = r
162016-20 无限制