题解 P2231 【[HNOI2002]跳蚤】

· · 题解

相比与楼下诸位的跳跃式思路，我个人比较笨，是用公式一步步推的，给出一个较严格的证明。

每次选一个数跳若干格，这就是所谓的“线性组合”。所以我们可以将问题规约为：如果这n+1个数的最大公约数是1，那么这个方案就是可行的。

记\delta_1(n)当n=1时得到1，其他都为0。那么这个计数就可以记为：

\sum_{a_1 = 1}^m \cdots \sum_{a_n = 1} ^ m\delta_1(\gcd(\gcd a, m))

考虑到判别函数\delta_1有莫比乌斯变换式

\delta_1(n) = \sum_{d|n} \mu(d)

此时参数空间满足d | a_i，d | m。

改变运算顺序，将d提到最前。

\text{ans} = \sum_{d|m} \mu(d) \left(\frac m d\right)^n

那么这个式子就是非常易于计算的了。

复杂度\Theta(\sqrt n \log n)。

#include <cstdio>

#define LOG(FMT...) // fprintf(stderr, "[LOG]: "FMT)

using namespace std;

typedef long long ll;

ll ans;
int n, m, pc;
int p[20];

ll pow(ll x, int k);
void dfs(int ind, int prod, int mu);

int main() {
    scanf("%d%d", &n, &m);
    int x = m;
    for (int d = 2; d * d <= m; ++d) {
        if (x % d == 0) {
            p[++pc] = d;
            while (x % d == 0)
                x /= d;
        }
    }
    if (x != 1)
        p[++pc] = x;
    dfs(1, 1, 1);
    printf("%lld\n", ans);
    return 0;
}

ll pow(ll x, int k) {
    ll ret = 1;
    while (k) {
        if (k & 1)
            ret *= x;
        k >>= 1;
        x *= x;
    }
    return ret;
}

void dfs(int ind, int prod, int mu) {
    if (ind == pc + 1) {
        ans += mu * pow(m / prod, n);
        return;
    }
    dfs(ind + 1, prod, mu);
    dfs(ind + 1, prod * p[ind], -mu);
}