【A 同源】2020上海高校程序设计竞赛暨第18届上海大学程序设计联赛夏季赛（同步赛）解题报告

题目地址：https://ac.nowcoder.com/acm/contest/6871

A 同源

题目描述 Compute 对于某些特殊的数字有着独特的爱好。 例如，有三个正整数 a, b, c 和某一个目标值 k，如果 gcd(a, b) = gcd(b, c) = gcd(a, c) = k，并且 a, b, c ≠ k ，那么他认为这三个数是一组好数。 其中 gcd(x, y) 表示整数 x 和 y 的最大公约数。 当然这不够刺激。现在 Compute 想要知道，如果已知三个数的和 n 和目标值 k，是否存在一组 a, b, c 可以让它们是一组好数。

输入描述 第一行输入一个整数 T (1 <= T <= 1000)，表示数据的组数。对于每组数据： 仅一行包含两个整数 n, k (1 ≤ n, k ≤ 10¹⁸)，分别表示 a, b, c 的和与目标值。

输出描述 对于每一组数据，在一行输出三个整数，中间以空格分隔，表示找到的一种方案。 如果有多种方案，任意输出其中一种即可。 特别地，如果没有满足条件的方案，在一行输出 -1 -1 -1。

思路
容易观察到两个特判情况一定是会输出-1 -1 -1的：一是 n 不能被 k 整除，二是 n / k < 10。
第一个情况很好理解，如果 n 不能被 k 整除，那么对于题目要求的一组 (a, b, c)，不可能有 a + b + c = n 成立。
排除了这一种情况，现在 n 一定是可以被 k 整除的了。此时，我们令 w = n / k，题目就可以转化为求三个互质的数，且这三个互质的数之和为 w 。显然可以观察到，最小的这样一组互质的数是(2, 3, 5)，于是第二种特判情况就出来了：如果 n / k < 10，肯定是无解的。
下面考虑如何构造出这样一组互质的数。首先要分 w 的奇偶两种情况。

1. 如果 w 是偶数
   考虑到质数中只有2是偶数，其余的全为奇数，所以 w 一定要分解为 2 + 奇质数 + 奇质数 的组合。于是我们可以确定 a = 2 * k，剩下要做的事就是确定 b 和 c 了。首先在程序中进行线性筛素数的预处理，拿到素数表。然后从 3 开始枚举素数 b ，直到找到 c = w - b - 2 且 c 和 b 互质（c 肯定与 2 互质，不用再判断），就成功找到了 b 和 c ，最后把 b 和 c 都乘上 k 即为最终答案。
2. 如果 w 是奇数
   考虑到质数中只有2是偶数，其余的全为奇数，所以 w 一定要分解为 奇质数 + 奇质数 + 奇质数 的组合。我们不妨确定 a = 3 * k，也就是把 w 分解为 3 + 奇质数 + 奇质数 的组合。剩下要做的事还是确定 b 和 c 。首先在程序中进行线性筛素数的预处理，拿到素数表。然后从 5 开始枚举素数 b ，直到找到 c = w - b - 3 且 c 和 b 互质 且 c 和 3 互质，就成功找到了 b 和 c ，最后把 b 和 c 都乘上 k 即为最终答案。

本题还有两个注意点：

1. 如果按照上述写法会挂，对拍了一阵发现过不了 n = 17, k = 1 这组数据，遂在输出时加上特判 c > 0 && a != k && b != k && c != k，最终过题。
2. 对于 w 是奇数的情况，我还无法证明为什么一定有一个是 3 * k。

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cmath>
#include<iostream>
#include<cstring>
using namespace std;
template<class _T>inline void read(_T &_a)
{
    bool f=0; char _c=getchar(); _a=0;
    while(_c<'0'||_c>'9'){ if(_c=='-') f=1; _c=getchar(); }
    while(_c>='0'&&_c<='9'){ _a=(_a<<3)+(_a<<1)-'0'+_c; _c=getchar(); }
    if(f) _a=-_a;
}
 
const int MAXN=1000002;
long long n,k,T,a,b,c,pri[MAXN];
bool npri[MAXN];
int pricnt;
 
inline void init()
{
    for (int i=2;i<=1000000;++i)
    {
        if(!npri[i]) pri[++pricnt]=i;
        for (int j=1;j<=pricnt;++j)
        {
            if(i*pri[j]>1000000) break;
            npri[i*pri[j]]=true;
            if(i%pri[j]==0) break;
        }
    }
}
 
int main()
{
    init();
    for(read(T);T;--T)
    {
        read(n);
        read(k);
        c=-1;
        if(n/k*k!=n || n/k<10)
        {
            printf("-1 -1 -1\n");
            continue;
        }
        n/=k;
        if(n&1)
        {
            a=3*k;
            for (int i=3;i<=pricnt&&(n-3-pri[i])>0;++i)
                if((n-3-pri[i])%pri[i]!=0&&(n-3-pri[i])%3!=0)
                {
                    b=pri[i]*k;
                    c=(n-3-pri[i])*k;
                    break;
                }
        } else {
            a=2*k;
            for (int i=2;i<=pricnt&&(n-2-pri[i])>0;++i)
                if((n-2-pri[i])%pri[i]!=0)
                {
                    b=pri[i]*k;
                    c=(n-2-pri[i])*k;
                    break;
                }
        }
        if(c>0&&a!=k&&b!=k&&c!=k) printf("%lld %lld %lld\n",a,b,c);
        else printf("-1 -1 -1\n");
    }
    return 0;
}