[ARC114A] Not coprime题解

zsh_haha · 2024-03-02 02:11:14 · 题解

题目大意

给定 n 个数，再找一个数，使找的数与这 n 个数中的每个数的最大公因数不等于 1。

思路讲解

一道考验数学知识的好题。

对于一个正整数 m，可以得到：

其中 k 为正整数，p_i 为质数，也是 m 的质因子。

若想使两个数的最大公因数不等于 1，那么这两个数必须至少有一个相同的质因子。

所以我们想找的数的所有质因子必须包含这 n 个数中每个数的所有质因子。

所以我们可以选若干个质数相乘使这些质数包含这 n 个数中每个数的所有质因子，相乘得到的结果就是我们要找的这个数。

由于这里的 a_i 范围很小，最大为 50，所以我们可以先列举出 50 以内的所有质数，再用深搜暴力枚举得出答案。

AC 代码

#include<bits/stdc++.h>
using namespace std;
long long pri[]={0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47};
long long n,a[50];
long long ans=1e18;//注意不能设1e9了 
void dfs(long long pro,int now){
    for(int i=1;i<=n;i++){
        if(__gcd(a[i],pro)==1){
            goto t1;
        }
    }
    ans=min(ans,pro);
    t1:;
    if(now==16){
        return;
    }
    dfs(pro*pri[now],now+1);
    dfs(pro,now+1);
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    dfs(1,1);
    cout<<ans;
    return 0;
}