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

jinfanhao · 2024-10-15 11:43:50 · 题解

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

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+1;
int n,op[N];
int check(int op){
    int sum=0;
    for(int i=2; i<=op/i; ++i){
        while(!(op%i)){
            ++sum;
            op/=i;
        }
    }
    if(op>1)++sum;
    return sum;
}
signed main(){
    scanf("%lld",&n);
    for(int i=1; i<=n; ++i)scanf("%lld",&op[i]);
    for(int i=1; i<=n; ++i){
        if(check(op[i])%2==1)printf("1 ");
        else printf("2 ");      
    }
    return 0;
}