CF900D-Unusual Sequences

2022-07-31 题解

题目大意：给定两个数x、y，求最大公约数为x，总和为y的数列数量。

令f(x, y)为最大公约数为x，总和为y的数列数量。

注意到：若y不能除尽x，f(x, y)=0恒成立。而若y能除尽x，数列中的每个数的值都至少为x。这样的话就相当于将 $\frac{y}{x}$ 分成若干个数相加。不难知道，求法总数是 $2^{\frac y x -1}$

但这不是全部。注意到：当 $\frac y x$ 分成的这若干个数的最大公约数（下面记作gt）大于1，得到的序列的最大公约数就不再是x，而是gt*x。因此需要减去最大公约数大于1的这些数列的数量。

所以就枚举所有的最大公约数gt，依次减去 $f(gt,\frac y x)$ 。递归计算下去。

#include <bits/stdc++.h>
#define int long long
using namespace std;
unordered_map<int, int> mp;
const long long mod = 1e9 + 7;
long long ksm(long long a, long long x)
{
    long long ret = 1 % mod;
    while (x)
    {
        if (x & 1)
            ret = ret * a % mod;
        a = a * a % mod;
        x >>= 1;
    }
    return ret;
}
int f(int x, int y)
{
    if (y % x > 0)
        return 0;
    if (x == y)
        return 1;
    int k = x * mod + y;
    if (mp.find(k) != mp.end())
        return mp[k];
    int n = y / x;
    int ret = ksm(2, n - 1) - 1, i;
    for (i = 2; i * i <= n; i++)
    {
        if (n % i == 0)
        {
            ret = (ret - f(i, n) + mod) % mod;
            if (n / i != i)
                ret = (ret - f(n / i, n) + mod) % mod;
        }
    }
    return mp[k] = ret;
}
signed main()
{
    int x, y;
    cin >> x >> y;
    cout << f(x, y);
    return 0;
}