[CF 900F]Unusual Sequence

danihao123 posted @ 2018年9月09日 20:58 in 题解 with tags codeforces 容斥原理 莫比乌斯反演 狄利克雷卷积 , 12 阅读
转载请注明出处:http://danihao123.is-programmer.com/

求有多少正整数序列,满足所有数的最大公约数为\(x\),所有数的和为\(y\)。

\(1\leq x, y\leq 10^9\)。

首先,如果\(x\)不是\(y\)的约数的话显然无解。

那么设\(r=\frac{y}{x}\),那么将\(\sum a_i = y\)两边除\(x\)的话右边就变成了\(r\)。问题就变成了要求和为\(r\),最大公约数为\(1\)。

然后求gcd恰为\(1\)很不好弄,我们试图将问题转化为gcd为\(c\)的倍数来做。那么对于给定的\(c\)(显然有\(\sigma_0(r)\)种),设\(m = \frac{r}{c}\),那么用隔板法可知合法序列有\(\sum_{i = 1}^{m}\binom{m - 1}{i - 1} = 2^{m - 1}\)。然后我们把至少转为恰好,这就是容斥原理的用武之地了,容斥系数显然要是莫比乌斯函数。

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <functional>
#include <utility>
using ll = long long;
const ll ha = 1000000007LL;
ll pow_mod(ll a, ll b) {
  ll ans = 1, res = a;
  while(b) {
    if(1LL & b) ans = ans * res % ha;
    res = res * res % ha; b >>= 1;
  }
  return ans;
}

const int N = 10000000;
bool vis[N + 5]; int prm[N + 5];
int mu[N + 5];
void process() {
  vis[1] = true; mu[1] = 1;
  int pcnt = 0;
  for(int i = 2; i <= N; i ++) {
    if(!vis[i]) {
      prm[pcnt ++] = i;
      mu[i] = ha - 1LL;
    }
    for(int j = 0; j < pcnt; j ++) {
      int v = i * prm[j];
      if(v > N) break;
      vis[v] = true;
      if(i % prm[j] == 0) {
        mu[v] = 0; break;
      } else {
        mu[v] = ha - mu[i];
      }
    }
  }
}
ll calc_mu(int n) {
  if(n <= N) return mu[n];
  // int m = floor(sqrt(n) + 0.5);
  int ret = 1;
  for(int i = 2; i * i <= n; i ++) {
    if(n % i == 0) {
      int th = 0;
      while(n % i == 0) {
        th ++; n /= i;
      }
      if(th == 1) {
        ret = ha - ret;
      } else {
        return 0;
      }
    }
  }
  if(n > 1) ret = ha - ret;
  return ret;
}

ll calc_delta(int x, int n) {
  ll th = pow_mod(2, (n / x) - 1) * calc_mu(x) % ha;
  return th;
}
ll solve(int n) {
  // int m = floor(sqrt(n) + 0.5);
  ll ret = 0;
  for(int i = 1; i * i <= n; i ++) {
    if(n % i == 0) {
      ret = (ret + calc_delta(i, n)) % ha;
      if(i * i != n) ret = (ret + calc_delta(n / i, n)) % ha;
    }
  }
  return ret;
}

int main() {
  process();
  int x, y; scanf("%d%d", &x, &y);
  if(y % x != 0) {
    puts("0");
  } else {
    printf("%I64d\n", solve(y / x));
  }
  return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter