询问 codeforces 问题的想法（Problem-483A Counterexample）

Question

问题link：http://codeforces.com/problemset/problem/483/A

You need to find three numbers (a, b, c), such that l ≤ a < b < c ≤ r, pairs (a, b) and (b, c) are coprime, and pair (a, c) is not coprime. The single line contains two positive space-separated integers l, r (1 ≤ l ≤ r ≤ 10^(18); r - l ≤ 50).

我想知道解决这个问题的思路。

编辑：

这是我的尝试：

#include<iostream>
#include<cstdlib>
using namespace std;
int main()
{
    int l, r, i, c;
    cin >> l >> r;
    c = r - l;

    if(c <= 50)
    {
        if(c >= 2)
        {
            for(i = l; i <= r; i++)
            {
                if(i % 2 == 0)
                {
                    cout << i << " " << i+1 << " " << i+2 << endl;
                    break;
                }
            }
        }
        else if(c <= 1)
        {
            cout << "-1" << endl;
        }
    }
}

我的代码有什么问题？站点上的错误消息是

Probably, the solution is executed with error 'uninitiaized value usage' on the line 10

Answer 1

如果 l 和 r 的距离小于 2，则不存在这样的三元组，因为我们希望它们完全不同。

如果他们的距离是2，唯一的可能就是选择l，l+1，l+2。如果 l 是偶数，那么它是一个有效的反例。但是，如果l是奇数，那么就没有这样的反例，因为l和l+1是互质的，l+1和l+2一定是互质的，但是l和l+2不能有2作为公因数因为他们是奇数。

如果距离大于2，就取a为至少和l一样大的最小偶数，return(a,a+1,a+2)。 a 和 a+2 有公因数 2.

显示尝试后编辑，这是一个可能的 C++ 代码：

#include<iostream>
#include<cstdlib>
using namespace std;
int main()
{
    long long l,r,i,c, first;
    cin >> l >> r;
    c=r-l;
    if ((c<2) || (c==2) && (l%2 == 1)){
        cout << "-1" << endl;
    }
    else{
        first = l + l % 2;
        cout << first << " " <<first+1 << " " << first+2 << endl;
    }
}

询问 codeforces 问题的想法（Problem-483A Counterexample）

Asking ideas of a codeforces problem (Problem-483A Counterexample)

math

functional-programming

brute-force

number-theory