Codeforces 1294C

题目大意：

给定一个n，问是否存在3个互不相同的，大于等于2的整数，满足a*b*c=n

解题思路：

可以把abc其中任意两个看作一个整体，例如a*b=d，那么可以发现d*c=n

所以d和c是n的因子

易得a和b也是n的因子

所以可以往n的因子这方面去考虑

题目就变成，是否存在3个不互相同的且大于等于2的n的因子，使得这三个因子的乘积为n

循环i=2~sqrt(n)，找出所有n的因子i和对应的n/i，储存起来

又可以想到，如果abc其中有任意一个数大于sqrt(n)，那么剩下两个数的乘积必定小于sqrt(n)

所以只需要枚举2~sqrt(n)中的因子，取出两个当作a和b，判断此时的c是否存在即可

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll> fac;//存2~sqrt(n)内的因子
set<ll> mfac;//存除了1和自身的所有的因子
void solve(){
    fac.clear();
    mfac.clear();
    ll n,i,j,d,d2,cnt;
    cin>>n;
    d=sqrt(n);
    for(i=2;i<=d;i++)
        if(n%i==0){
            fac.push_back(i);
            mfac.insert(i);
            mfac.insert(n/i);
        }
    cnt=fac.size();
    for(i=0;i<cnt;i++)
        for(j=i+1;j<cnt;j++){
            d=fac[i]*fac[j];//枚举两个数乘积
            d2=n/d;
            if(n%d==0&&d2!=fac[i]&&d2!=fac[j]&&mfac.find(d2)!=mfac.end()){//如果乘积d是n的因子，且此时三个数互不相同，且n/d也是n的因子，说明找到了答案
                cout<<"YES
"<<fac[i]<<' '<<fac[j]<<' '<<n/d<<'
';
                return;
            }
        }
    cout<<"NO
";
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int T;cin>>T;
    while(T--)
        solve();
    
    return 0;
}

另，还可以根据a,b,c都为n的因子这个定理，在找到第一个因子a后，把b,c看作是n/a的因子

那么就可以只找两个因子就结束循环直接进行判断

#include<bits/stdc++.h>
using namespace std;
void solve(){
    int n,i,cnt=0,d,ar[3];
    cin>>n;
    for(i=2;i*i<=n;i++)
        if(n%i==0){
            ar[cnt++]=i;
            n/=i;
            if(cnt==2)
                break;
        }
    if(cnt==2){
        ar[2]=n;
        sort(ar,ar+3);
        if(ar[0]!=ar[1]&&ar[1]!=ar[2]){
            cout<<"YES
"<<ar[0]<<' '<<ar[1]<<' '<<ar[2]<<'
';
            return;
        }
    }
    cout<<"NO
";
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int T;cin>>T;
    while(T--)
        solve();
    
    return 0;
}