首页 > 技术文章 > codeforces 483A. Counterexample 解题报告

windysai 2014-10-25 10:56 原文

题目链接:http://codeforces.com/problemset/problem/483/A

题目意思:给出一个区间 [l, r],要从中找出a, b, c,需要满足 a, b 互质,b, c 互质,但是 a, c 不互质,也就是除了 1 之后还有其他公约数。要求 1<= a < b < c <= r,也就是 a, b, c 两两不相等的。如果找不出则输出 -1。

    首先很容易知道,如果 [l, r] 这个区间只有两个数,那么肯定没有答案。还有一种情况是,如果 [l, r] 这个区间只有 三个数,且 l,r 同时为奇数,那么都是无解。除此都可以找出 3 个数满足条件。这三个数不难找出:偶数,奇数,偶数(连续的三个数) 绝对符合条件。找出第一个符合条件的最小偶数,再这样输出即可。

    有个比较卑鄙的地方是 l 有可能等于 r,此时也是无解的。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <algorithm>
 6 using namespace std;
 7 
 8 typedef __int64 LL;
 9 
10 int main()
11 {
12     LL l, r, interval;
13     while (scanf("%I64d%I64d", &l, &r) != EOF)
14     {
15          interval = r - l;
16          if (interval == 0 || interval == 1 || (interval == 2 && l & 1  && r & 1))
17             printf("-1\n");
18          else
19          {
20              while (l & 1 && l < r)
21                  l++;
22              printf("%I64d %I64d %I64d\n", l, l+1, l+2);  // even, odd, even
23          }
24     }
25     return 0;
26 }

 

推荐阅读