题目地址: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 ≤ 1018),分别表示 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;
}
©著作权归作者所有

发表评论

正在加载 Emoji