A - Not coprime

题意

$N$ 個の $2$ 以上 $50$ 以下の整数 $X_1,X_2,\ldots,X_N$ が与えられます。全ての $i=1,2,\ldots,N$ について次の条件を満たす正の整数 $Y$ のうち、最小のものを求めてください。

• $X_i$ と $Y$ は互いに素でない

解析

观察到 $50$ 以内的素数很少，我们只需要枚举 $Y$ 包含的素因数即可。

实现

#include <bits/stdc++.h>

const int maxn = 52;

unsigned long long int gcd(unsigned long long int a, unsigned long long int b){
    return b ? gcd(b, a % b) : a;
}

bool vist[maxn];
int prime[maxn], cnt;

int main(){
    for(int i = 2; i <= 50; ++i){
        if(!vist[i]) prime[++cnt] = i;
        for(int j = 1; j <= cnt && i * prime[j] <= 50; ++j){
            vist[i * prime[j]] = true;
            if(i % prime[j] == 0) break;
        }
    }
    static int x[maxn], n;
    std::scanf("%d", &n);
    for(int i = 1; i <= n; ++i) std::scanf("%d", x + i);
    unsigned long long int ans = 0ull - 1ull;
    for(int i = 0; i < (1 << cnt); ++i){
        unsigned long long int res = 1ull;
        for(int j = 0; j < cnt; ++j)
            if(i & (1 << j))
                res *= prime[j + 1];
        bool flag = true;
        for(int j = 1; j <= n; ++j)
            if(gcd(x[j], res) == 1){
                flag = false;
                break;
            }
        if(!flag) continue;
        ans = std::min(ans, res);
    }
    std::printf("%llu\n", ans);
    return 0;
}

来源

AtCoder Regular Contest 114 A - Not coprime

评论