900D - Unusual Sequences - CodeForces Solution

// In the name of Allah

#include<algorithm>
#include<iostream>
#include<cassert>
#include<iomanip>
#include<cstring>
#include<sstream>
#include<numeric>
#include<string>
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
#include<cmath>
#include<set>
#include<map>

using namespace std;

typedef long long ll;

#define pb push_back
#define all(x) x.begin(),x.end()
#define fr first
#define sec second


//####################################################
constexpr ll M = 1e9 + 7;
int x, y;
map<int, ll> mp;
vector<int> d;

//####################################################


ll pw(ll a, ll b){
    if (!b)
        return 1;
    ll re = pw(a, b / 2);
    re *= re;
    re %= M;
    if (b % 2){
        re *= a;
        re %= M;
    }
    return re;
}

void solve(){
    cin >> x >> y;
    if (y % x){
        cout << 0 << '\n';
        return;
    }
    y /= x;
    for (int i = 1; i * i <= y; i++)
        if (y % i == 0)
            d.pb(i);
    int n = d.size();
    for (int i = n - 1; i >= 0; i--)
        d.pb(y / d[i]);
    for (auto di : d){
        mp[di] = pw(2, di - 1);
        for (int i = 1; i * i <= di; i++){
            if (di % i == 0 && di != i){
                mp[di] -= mp[i];
                if (di / i != i && i != 1)
                    mp[di] -= mp[di / i];
            }
            if (mp[di] < 0)
                mp[di] += M;
        }
    }
    cout << mp[y] << '\n';





}

int main(){
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    while (t--)
            solve();
    return 0;
}