「题解」Unusual Sequences

题意：输入 $x,y$，求有多少个数列满足其gcd为 $x$，和为 $y$。
这里提供一个不使用反演的清奇思路……

设 $f(s,g)$ 表示和为 $s$ ,gcd为 $g$ 的数列的数量，容易发现以下性质：

$$\begin{aligned} f(s,g)&=0, \text{ }g\nmid s \newline f(s,g)&=f(s/g,1), \text{ } g|s \end{aligned}$$

我们知道和为 $s$ 的数列应当有 $2^{s - 1}$ 个，即把 $s$ 看成 $s$ 个1，然后插上 $s - 1$ 个隔板。那么有：

$$\begin{aligned} 2^{s - 1} &= \sum\limits_{g=1}^s f(s,g)
\newline &=\sum\limits_{g | s}f(s,g)
\newline &=\sum\limits_{g | s}f(s/g,1)
\end{aligned}$$

移一下项，得到：
$$ f(s,1)=2^{s - 1}-\sum\limits_{g|s,g>1}f(s / g,1) $$

设 $f[s]$ 表示 $f(s, 1)$ ，得到递推方程：
$$ f[s] = 2^{s - 1}-\sum\limits_{g|s,g>1}f[s/g]$$

直接做是 $O(n)$ 的，但是容易知道有些位置的值是用不到的。开一个 map 储存 $f[]$ 数组，大力递推计算，参考杜教筛的复杂度，大约是 $O(n^{\frac{3}{4}})$，但是实际上跑得出奇的快。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<map>
using namespace std;

#define LL long long
const int P = 1e9+7;

int x,y;

int qp(int a,int b){
    int r = 1;
    while(b){
        if(b & 1) r = (1ll * a * r) % P;
        a = (1ll * a * a) % P; b >>= 1;
    }
    return r;
}
map<int, int> f;
int dfs(int s){
    if(s == 1) return 1;
    if(f.count(s)) return f[s];
    int r = qp(2, s - 1);
    for(int g = 2;g * g <= s;g++){
        if(s % g) continue;
        if(g * g == s) r = (r - dfs(g) + P) % P;
        else r = ((r - dfs(s / g) - dfs(g)) % P + P) % P;
    }
    return f[s] = (r - 1 + P) % P;
}

int main()
{
    // freopen("_in.in", "r", stdin);

    scanf("%d%d", &x, &y);
    if(y % x) puts("0");
    else printf("%d", dfs(y / x));
}