hdu5514

题意

$m$ 个石子绕成一圈，编号$[0, m - 1]$。有 $n$ 个青蛙从 $0$ 号石子出发，给出每个青蛙的步长，青蛙无限跑圈。问哪些石子至少被一个青蛙经过，求这些石子的编号之和。

分析

假设某个青蛙的步长 $x$，则一共会经过 $ \frac{m - 1}{x} + 1$ 个石子（包括 $0$ ）。可以用等差数列求和公式计算贡献。

然后找出 $m$ 的所有因子并考虑哪些因子可能要计算贡献。

例如步长为 $2$ 和 $3$ 的计算后，步长为 $6$ 的情况被计算了两次（或者说 $6$ 的倍数的编号被计算了两次），应该减去一次，用一个数组记录某个步长被计算了几次贡献，在统计答案的时候减去即可。

code

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 1e4 + 10;

int a[MAXN];

int fac[MAXN];

int vis[MAXN]; // vis[i]表示fac[i]是否可能要计算贡献，如果为 0 一定不计算贡献

int num[MAXN]; // num[i]表示fac[i]被计算了几次贡献

int main() {

    int T, kase = 1;

    scanf("%d", &T);

    while(T--) {

        memset(vis, 0, sizeof vis);

        memset(num, 0, sizeof num);

        int n, m;

        scanf("%d%d", &n, &m);

        int fc = 0;

        for(int i = 1; i * i <= m; i++) {

            if(m % i == 0) {

                fac[fc++] = i;

                if(i * i != m) fac[fc++] = m / i;

            }

        }

        sort(fac, fac + fc);

        for(int i = 0; i < n; i++) {

            scanf("%d", &a[i]);

            a[i] = __gcd(a[i], m);

            for(int j = 0; j < fc; j++) {

                if(fac[j] % a[i] == 0) {

                    vis[j] = 1;

                }

            }

        }

        ll ans = 0;

        for(int i = 0; i < fc - 1; i++) {

            ll k = (m - 1) / fac[i];

            ans += (k + 1) * k * fac[i] / 2 * (vis[i] - num[i]);

            for(int j = i + 1; j < fc - 1; j++) {

                if(fac[j] % fac[i] == 0) {

                    num[j] += vis[i] - num[i];

                }

            }

        }

        printf("Case #%d: %lld\n", kase++, ans);

    }

    return 0;

}

巴特西

hdu5514

hdu5514

题意

分析

code

最新文章

热门文章