出题人题解 | #禁止动规#

原题解链接：https://ac.nowcoder.com/discuss/149990

首先，裴蜀定理告诉我们，对于如下关于 $x_{i}$ 的整数方程:

\sum_{i=1}^{n} a_{i} x_{i}=k

有解的条件是 $\operatorname{gcd}\left(a_{1}, a_{2}, a_{3}, \ldots, a_{n}\right) \mid k$

在这道题中，是求 $\operatorname{gcd}\left(x_{1}, x_{2}, x_{3}, \ldots, x_{n}\right) \mid 1$ 的方案数

即 $\operatorname{gcd}\left(x_{1}, x_{2}, x_{3}, \ldots, x_{n}\right)=1$ 的方案数

于是推式子:

\begin{aligned} & \sum_{i_{1}=1}^{m} \sum_{i_{2}=1}^{m} \cdots \sum_{i_{n}=1}^{m}\left[\operatorname{gcd}\left(i_{1}, i_{2}, \ldots i_{n}\right)=1\right] \\ =& \sum_{i_{1}=1}^{m} \sum_{i_{2}=1}^{m} \cdots \sum_{i_{n}=1}^{m} \sum_{t \operatorname{gcd}\left(i_{1}, i_{2}, \ldots i_{n}\right)} \mu(t) \\ =& \sum_{t=1}^{m} \mu(t) \sum_{i_{1}=1}^{m} \sum_{i_{2}=1}^{m} \cdots \sum_{i_{n}=1}^{m}\left[t\left|i_{1} \wedge t\right| i_{2} \wedge \cdots \wedge t \mid i_{n}\right] \\ =& \sum_{t=1}^{m} \mu(t)\left\lfloor\frac{m}{t}\right\rfloor^{n} \end{aligned}



#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
const int N = 2.2e7 + 10;
ll n, m, ans;

// ---------------
ll mu[N], pri[int(1e7) + 10], calc[int(4e5) + 10];
bool vis[int(4e5) + 10], vvv[N];
int tot;
void init() {
    mu[1] = 1;
    for(int i = 2 ; i < N ; ++ i) {
        if(!vvv[i]) mu[i] = - 1, pri[++ tot] = i;
        for(int j = 1 ; j <= tot && i * pri[j] < N ; ++ j) {
            vvv[i * pri[j]] = 1;
			if(i % pri[j] == 0) break;
            else mu[i * pri[j]] = -mu[i];
        }
    }
    for(int i = 1 ; i < N ; ++ i) mu[i] += mu[i - 1];
}
// ---------------

ll sol(ll x) {
    if(x < N) return mu[x];
    if(vis[m / x]) return calc[m / x];
    vis[m / x] = 1;
    ll sum = x >= 1;
    for(ll i = 2, j ; i <= x ; i = j + 1) {
        j = x / (x / i);
        sum -= sol(x / i) * (j - i + 1);
    }
    return calc[m / x] = sum;
}

inline ll pw(ll a, ll b) {
    ll r = 1;
    for( ; b ; b >>= 1, a *= a) if(b & 1) r *= a;
    return r;
}

int main() {
	ios :: sync_with_stdio(0);
    init();
    cin >> n >> m;
    for(ll i = 1, j ; i <= m ; i = j + 1) {
        j = m / (m / i);
        ans += pw(m / i, n) * (sol(j) - sol(i - 1));
    }
    cout << ans;
}