求有多少正整数序列，满足所有数的最大公约数为\(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;
}

• 相关文章
• 全局相关文章