禁止动规_牛客博客

选出来的 $n$ 个数能凑成 $-1$ 或者 $1$ 必然有一个性质， $gcd(a_1, a_2, \dots, a_n) = 1$ 。
$ $\sum_{a_1 = 1} ^{m} \sum_{a_2 = 1} ^{m} \dots \sum_{a_{n} = 1} ^{m} \gcd(a_1, a_2, \dots, a_n) = 1\\ \sum_{a_1 = 1} ^{m} \sum_{a_2 = 1} ^{m} \dots \sum_{a_{n} = 1} ^{m} \sum_{k \mid \gcd(a_1, a_2, \dots, a_{n}))} \mu(k)\\ \sum_{k = 1} ^{m} \mu(k) \lfloor\frac{m}{k} \rfloor ^ n\\ 最后只要数论分块加上\mu的杜教筛即可\\$ $

#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ull;
typedef long long ll;

const int N = 2e7 + 10;

int prime[N], cnt;

ull mu[N];

bool st[N];

void init() {
  mu[1] = 1;
  for (int i = 2; i < N; i++) {
    if (!st[i]) {
      prime[++cnt] = i;
      mu[i] = -1;
    }
    for (int j = 1; j <= cnt && 1ll * i * prime[j] < N; j++) {
      st[i * prime[j]] = 1;
      if (i % prime[j] == 0) {
        break;
      }
      mu[i * prime[j]] = -mu[i];
    }
  }
  for (int i = 1; i < N; i++) {
    mu[i] += mu[i - 1];
  }
}

map<ll, ull> mp;

ull Djs_mu(ll n) {
  if (n < N) {
    return mu[n];
  }
  if (mp.count(n)) {
    return mp[n];
  }
  ull ans = 1;
  for (ll l = 2, r; l <= n; l = r + 1) {
    r = n / (n / l);
    ans -= (r - l + 1) * Djs_mu(n / l);
  }
  return mp[n] = ans;
}

ull quick_pow(ull a, ll n) {
  ull ans = 1;
  while (n) {
    if (n & 1) {
      ans = ans * a;
    }
    a = a * a;
    n >>= 1;
  }
  return ans;
}

int main() {
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  // ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  init();
  ull n, m, ans = 0;
  cin >> n >> m;
  for (ull l = 1, r; l <= m; l = r + 1) {
    r = m / (m / l);
    ans += quick_pow(m / l, n) * (Djs_mu(r) - Djs_mu(l - 1));
  }
  cout << ans << "\n";
  return 0;
}