题意

\(m\) 个石头围成一个圆圈,编号从 \(0\)\(m - 1\)\(n\) 只青蛙,编号从 \(1\)\(n\)。第 \(i\) 只青蛙只能跳 \(a_i\) 步,即从 \(j\ mod\ m\)\((j + a_i)\ mod\ m\)。求被青蛙踩过的石头的编号和,每个石头的编号只算一次。

不超过 \(20\) 组数据,其中,\(1 \leq m \leq 10^9\)\(1 \leq n \leq 10^4\)

题解

\(g_i = gcd(a_i, m)\),则第 \(i\) 只青蛙,踩过的石头的编号为 \(0, g_i, 2g_i, 3g_i, \cdots, 0\)

如果直接通过等差数列求和公式求和,会有很多石头的编号被重复计算。

由于只有编号为 \(m\) 的因子的石头会被踩到,故对 \(m\) 的因子进行分类。

\(gcd(x, m) = t\),则 \(x\) 属于第 \(t\) 类,其中 \(x\)\(m\) 的因子,且若存在 \(x\ mod \ g_i = 0\),则 \(t \ mod \ g_i = 0\)

若存在 \(t \ mod \ g_i = 0\),则第 \(t\) 类的贡献为 \(\sum_{gcd(x, m) = t}^{x < m}x = t \times \sum_{gcd(y, m) = 1}^{y < m \div t}\)

代码

 1 2 3 4 5 6 7 8 91011121314151617181920212223242526272829303132333435363738394041424344454647484950
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 1e4 + 5;
int a[MAX_N], g[MAX_N];
int fct[MAX_N];
ll phi(ll x) {
    ll ret = x;
    for (ll i = 2; i * i <= x; i++)
        if (x % i == 0) {
            ret -= ret / i;
            while (x % i == 0)
                x /= i;
        }
    if (x > 1)
        ret -= ret / x;
    return ret;
}
int main() {
    int T;
    int cas = 0;
    scanf("%d", &T);
    while (T--) {
        int n, m;
        scanf("%d%d", &n, &m);
        for (int i = 0; i < n; i++)
            scanf("%d", &a[i]), g[i] = __gcd(a[i], m);
        sort(g, g + n);
        int tot = unique(g, g + n) - g;
        int cnt = 0;
        fct[cnt++] = 1;
        for (int i = 2; i * i <= m; i++)
            if (m % i == 0) {
                if (i * i == m)
                    fct[cnt++] = i;
                else
                    fct[cnt++] = i, fct[cnt++] = m / i;
            }
        ll ans = 0;
        for (int i = 0; i < cnt; i++) {
            for (int j = 0; j < tot; j++)
                if (fct[i] % g[j] == 0) {
                    ans += phi(m / fct[i]) * m / 2;
                    break;
                }
        }
        printf("Case #%d: %lld\n", ++cas, ans);
    }
    return 0;
}
comments powered by Disqus