F-Frogs

F. Frogs

题目描述：

$ m $ 个石头围成一圈， $ n $ 只青蛙从 $ 0 $ 开始跳，第 $ i $ 只青蛙跳 $ a_i $ 步，求所有能被跳到的石头的编号的和。

数据范围：
$ 1\le n \le 10^4,1\le m \le 10^9, 1\le a_i \le 10^9 $

题解：

首先可以推出第 $ i $ 只青蛙能够跳到 $ g_i = \gcd(a[i], m) $ 倍数的位置，而 $ gcd(a[i], m) $ 一定是 $ m $ 的因子。关键是 $ g_i $ 的倍数有许多重复的地方，关键是去掉这些重复的地方。可以使用容斥原理，对每一个 $ m $ 的因子，看看重复了多少次，可以枚举 $ \sqrt{m} $ 内的，降低复杂度。

也有欧拉函数的做法。具体可以参考这里

这个证明关键就是 $ \gcd(x, i) = \gcd(x, x - i) = 1 $ ，使用更相减损术可以证明，所以很容易证明该结论。

代码：

using namespace std;
using namespace FAST_IO;
const ll mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-5;
const int maxn = 1e4 + 10;
const int maxm = 1e5 + 10;
int t, n, m, k;
ll a[maxn];

bool check(int x)
{
    for (int i = 1; i <= n; i++)
    {
        if (x % a[i] == 0)
            return true;
    }
    return false;
}

ll phi(ll x)
{
    ll ans = x;
    for (int i = 2; i * i <= x; i++)
    {
        if (x % i == 0)
        {
            ans = ans / i * (i - 1); // p^k * (p - 1)
            while (x % i == 0)
                x /= i;
        }
    }
    if (x > 1)
        ans = ans / x * (x - 1);
    return ans;
}
int main()
{
// #define COMP_DATA
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    int Tcase;
    read(Tcase);
    for (int tcase = 1; tcase <= Tcase; tcase++)
    {
        read(n, m);
        for (int i = 1, x; i <= n; i++)
        {
            read(x);
            a[i] = __gcd(x, m);
        }
        n = unique(a + 1, a + 1 + n) - a - 1;
        ll ans = 0;
        for (int i = 1; i * i <= m; i++)
        {
            if (m % i == 0)
            {
                if (check(i))
                {
                    ans += phi(m / i);
                }
                if (i == 1 || i * i == m)
                    continue;
                if (check(m / i))
                {
                    ans += phi(i);
                }
            }
        }
        ans = ans * m / 2;
        printf("Case #%d: %lld\n", tcase, ans);
    }
    return 0;
}