自动搬运

查看原文

来自洛谷，原作者为

	Elegia irony

搬运于2025-08-24 21:35:25，当前版本为作者最后更新于2018-01-04 16:59:00，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

每次选一个数跳若干格，这就是所谓的“线性组合”。所以我们可以将问题规约为：如果这$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);
}