526互联

Codechef - N Triplets（构造+观察）

发布时间 2023-08-13 22:40:28作者: ChebyshevTST

题目大意

  对于一个正整数N，需要找到三个不同的数字A，B，C，使得三个数当中任意两个数字相乘都是N的约数，另外还要使得A，B，C三个数字乘积是N的整数倍数。最后输出三个数字（如果有多种组合，输出任意一种即可），如果找不到满足条件的则输出-1。

 

思路

  注意到1必然是其中一个约数，另外我们可以注意到素数显然无解（素数只有1和其本身是因子）。对于约数有三个的数字这种情况，比如25，约数有1，5，25，虽然三者相乘是25的倍数，但是5和25相乘得出125，不是25的因数；对于偶数的4亦同理。将这三种情况特殊讨论后，后面的步骤就按照正常思路即可。举个例子，对于数字27，可取1，3，9，对于数字28，可取1，2，14。因此构造方式为，奇数（1，非N本身的约数，非N本身的约数），偶数（1，2，N÷2）。

 

代码

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#pragma GCC optimize(2)
#define int long long 
const int mod = 1e9 + 7;
const int N = 3e5;
int s[N];


bool isprime(int n) {
    if (n <= 1) return false;
    for (int i = 2; i <= n / i; ++i) {
        if (n % i == 0) return false;
    }
    return true;
}

vector<int> div(int n) {
    vector<int> v{1, n};
    for (int i = 2; i <= n / i; ++i) {
        if (n % i == 0) {
            v.push_back(i);
            if (n / i != i) v.push_back(n / i);
        }
    }
    return v;
}


void solve() {
    int n;
    cin >> n;
    if (isprime(n)) cout << "-1" << endl;
    else {
        vector<int> v = div(n);
        if (size(v) < 4) {
            cout << "-1" << endl;
            return;
        }
        if (n & 1) {
            cout << "1 " << v[2] << ' ' << v[3] << endl; 
        } else {
            cout << "1 2 " << n / 2 << endl;
        }
    }
}


signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    while (n--) {
        solve();
    }

    return 0;
}

 

题目链接在这里：N Triplets - Problems - CodeChef