同源

比较复杂的思维题

题目描述
Compute 对于某些特殊的数字有着独特的爱好。

例如，有三个正整数 a, b, c 和某一个目标值 k，如果 \gcd(a,b)=\gcd(b,c)=\gcd(a,c)=kgcd(a,b)=gcd(b,c)=gcd(a,c)=k，并且 a,b,c \neq ka,b,c

​
=k ，那么他认为这三个数是一组好数。 其中\gcd(x,y)gcd(x,y)表示整数 x 和 y 的最大公约数。

当然这不够刺激。现在 Compute 想要知道，如果已知三个数的和 n 和目标值 k，是否存在一组 a, b, c 可以让它们是一组好数。
输入描述:
第一行输入一个整数 T (1\leq T \leq 10001≤T≤1000)，表示数据的组数。对于每组数据：

仅一行包含两个整数 n, k (1\leq n,k \leq 10^{18}1≤n,k≤10
18
)，分别表示 a, b, c 的和与目标值。
输出描述:
对于每一组数据，在一行输出三个整数，中间以空格分隔，表示找到的一种方案。

如果有多种方案，任意输出其中一种即可。

特别地，如果没有满足条件的方案，在一行输出 -1 -1 -1。
示例1
输入
复制
2
20 2
12 2
输出
复制
4 6 10
-1 -1 -1

题目分析

1. 起初刚刚看到这个题目的时候我是一点思路都没有，后面看大佬的代码才慢慢理解一点点，直到现在我还是有点懵，但是希望写着写着就能明白吧
2. 首先我们要进行一次打表，把所有的质因子都存进一个数组里，因为后序我们会用得到，题目求的是有共同最大公约数的三个数，那么我们用三个数都除以最大公约数，那么剩下的就是三个互质的数，题目里给的是三个数的和，所以代码里只需要遍历一下就可以，我们把三个数求出来然后直接乘以最大公约数就是题目的答案
3. 另外我们需要特判，因为如果三个数都有共同的最大公约数，那么他们的和也是有相同的最大公约数，如果他们的和对最大公约数取模有剩余那么就不用继续后序的操作了，这必定求不出满足题目条件的数
4. 还有就是说abc不能出现其中一个数是1，这个我不是很理解

   #include <bits/stdc++.h>
   #define ll long long
   using namespace std;
   ll prime[110], cnt;
   void init()//初始化打表
   {
     prime[1] = 1;
     int x = 2;
     cnt = 1;
     while (cnt <= 100)
     {
         int flag = 0;
         for (int j = 2; j <= x / 2; j++)
             if (x % j == 0)
             {
                 flag = 1;
                 break;
             }
         if (!flag)
             prime[++cnt] = x;
         x++;
     }
   }
   int main()
   {
     init();
     int t;
     ll n, k;
     scanf("%d", &t);
     while (t--)
     {
         scanf("%lld%lld", &n, &k);
         if (n % k)
         {
             printf("-1 -1 -1\n");
             continue;
         }
         ll num = n / k;
         if (num < 10 || num == 11 | num == 13 || num == 17)
         {
             printf("-1 -1 -1\n");
             continue;
         }
         int flag = 0;
         for (int i = 1; i <= 100; i++)
         {
             for (int j = i + 1; j <= 100; j++)
             {
                 ll x = num - prime[i] - prime[j];
                 if (x > 1 && x != prime[i] && x != prime[j] && x % prime[i] && x % prime[j])
                 {
                     printf("%lld %lld %lld\n", prime[i] * k, prime[j] * k, x * k);
                     flag = 1;
                     break;
                 }
             }
             if (flag)
                 break;
         }
     }
     return 0;
   }