AtCoder Beginner Contest 182 解题报告

abc182_b Almost GCD

AtCoder Beginner Contest 182 第二题,模拟。

题目链接:B – Almost GCD

题意翻译

  • 给你一个长度为 \( n \) 的数列 \( a _ i \);
  • 定义 超级公因数 \( k \geq 2 \) 为,对于 \( a _ i \) 从中所有的 \( k \) 个元素,均能被 \( k \) 整除,使得这样的选法最多;
  • 有多种解法请输出任意一种;
  • 数据范围:\( 1 \leq n \leq 100 \),\( 2 \leq a _ i \leq 10 ^ 3 \)。

题解

不难发现,答案肯定小于等于 \( \max \{ a _ i \} \),因为要是它们的因数。

我们不妨枚举答案,统计可以被 \( k \) 整除的数的个数,不难发现,个数越多,选法越多,所以只需要除一遍即可。

#include <bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++)
static char buf[100000], *p1 = buf, *p2 = buf;
inline int read(void)
{
    reg bool f = false;
    reg char ch = getchar();
    reg int res = 0;
    while (!isdigit(ch))
        f |= (ch == '-'), ch = getchar();
    while (isdigit(ch))
        res = 10 * res + (ch ^ '0'), ch = getchar();
    return f ? -res : res;
}

const int MAXN = 100 + 5;

int n;
int a[MAXN];

int main(void)
{
    n = read();  //读入 n
    int Max = 0; //定义最大值
    for (reg int i = 1; i <= n; ++i)
    {
        a[i] = read();        //读入 a[i]
        Max = max(Max, a[i]); //求最大值
    }
    int ans = 0, gcd = 0;              //ans 表示答案,gcd 为倍数个数
    for (reg int i = 2; i <= Max; ++i) //枚举答案
    {
        reg int tot = 0;
        for (reg int j = 1; j <= n; ++j)
            if (!(a[j] % i)) //能被整除
                ++tot;       //计数
        if (tot > gcd)
            ans = i, gcd = tot; //更新答案
    }
    printf("%d\n", ans); //输出答案
    return 0;
}
Pages: 1 2 3 4 5 6 7 8