Codeforces Round #450 (Div. 2) D.Unusual Sequences (数学)

题目链接：

http://codeforces.com/contest/900/problem/D

题意：

给你 (x) 和 (y)，让你求同时满足这两个条件的序列的个数：

(a_1, a_2, ..., a_n (1 ≤ a_i))。

$ 1.$ $gcd(a_1, a_2, ..., a_n) = x $

$ 2.$ (sum_{i=1}^{n}a_i = y)

题解：

可以发现，当(y\%x!=0)时，满足条件的序列不存在。让(f(t))表示满足序列和为的 (t)，且(gcd) 为 (1) 的序列的个数。那么答案就是 (f(frac{y}{x}))。

显然，用隔板法可以证明，把一个数 (x) 分解成可以由几个数组成的序列有(2^{x-1})个，假设(k=frac{y}{x})，把其中是质数的情况保留，把非质数的情况减去就可以了，这里用记忆化，容斥一下就可以得到答案了。

代码：

#include<bits/stdc++.h>

using namespace std;

const int mod = 1e9+7;
#define ll long long

std::map<int, int> mp;
ll qpower(ll a,ll b,ll mod)
{
    ll ans = 1;
    while(b>0)
    {
        if(b&1) ans=(ans*a)%mod;
        b>>=1;
        a=(a*a)%mod;
    }
    return ans;
}
ll solve(int x)
{
  if(x==1)return 1;
  if (mp.count(x)) {
    return mp[x];
  }
  mp[x] = qpower(2,x-1,mod);
  for(int i=2;i*i<=x;i++) {
    if(x%i==0){
      mp[x] = (mp[x] - solve(x/i) + mod) % mod;
      if(i!=x/i){
        mp[x] = (mp[x] - solve(i) + mod) % mod;
      }
    }
  }
  mp[x] = (mp[x] - solve(1) + mod) % mod;
  return mp[x];
}
int x,y;
int main(int argc, char const *argv[]) {
  std::cin >> x >> y;
  if(y%x!=0){
    std::cout << "0" << '
';
    return 0;
  }
  std::cout << solve(y/x) << '
';
  return 0;
}