题意

\(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 91011121314151617181920212223242526272829303132333435363738394041424344454647484950515253
#include <cstdio>
#include <cstring>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
using namespace std;
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