题解：P11124 [ROIR 2024 Day 2] 数组划分

tkm2013 · 2024-10-15 11:34:46 · 题解

传送门

在这道题目中， p 是一个质数，两个数之间的只差一个质因数就不能放在一起，所以只要差两个以上个质因数，就可以凡在一起了。如果两个数的质因数个数奇偶性相同，那这两个数质因数的差就绝对 \ge 2 所以我们来判断所有数的质因数个数，为奇数放到一组，为偶数放到另一组。

Code

#include<bits/stdc++.h>
using namespace std;
int n;
int f(int k){//
    int cnt=0;
    for(int i=2;i<=k/i;i++){//进行质因数分解
        while(k%i==0){
            cnt++;
            k/=i;
        }
    } 
    if(k>1){
        cnt++;
    }
    return cnt;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        int a;
        cin>>a;
        if(f(a)&1){//是奇数放到一组
            cout<<1<<' ';
        }else{
            cout<<2<<' ';//是偶数放到一组
        }
    }
    return 0;
}