题目链接：
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" << '\n';
return 0;
}
std::cout << solve(y/x) << '\n';
return 0;
}
转载于:https://www.cnblogs.com/LzyRapx/p/8032075.html
