CF900D 【Unusual Sequences】

#include <bits/stdc++.h>
#define ll long long
const ll mod = 1e9 + 7;
std::map<int, int> m;
std::vector<int> v, vec;
int fast_pow(ll a, ll n)
{
    int ret = 1;
    while (n)
    {
        if (n & 1)
            ret = (1ll * ret * a) % mod;
        a = (1ll * a * a) % mod;
        n >>= 1;
    }
    return ret;
}
int solve(int x)
{
    if (m[x])
        return m[x];
    if (x == 1)
    {
        m[x] = 1;
        return x;
    }
    int sum = 0;
    int s = sqrt(x);
    for (int i = 1; i <= s; i++)
    {
        if (x % i == 0)
        {
            if (i == 1 || i * i == x)
                sum = (sum + solve(i)) % mod;
            else
                sum = (sum + solve(i) % mod + solve(x / i) % mod) % mod;
        }
    }
    sum = (fast_pow(2, x - 1) - sum + mod) % mod;
    m[x] = sum;
    return sum;
}
int main()
{
    ll x, y;
    std::cin >> x >> y;
    if (y % x != 0)
        return 0 * printf("0");
    y /= x;
    std::cout << solve(y);
    return 0;
}