Today on Informatics class Nastya learned about GCD and LCM (see links below). Nastya is very intelligent, so she solved all the tasks momentarily and now suggests you to solve one of them as well.

We define a pair of integers (a,b)good, if GCD(a,b)=x and LCM(a,b)=y, where GCD(a,b)denotes the greatest common divisor of a and b, and LCM(a,b)denotes the least common multiple of a and b.

You are given two integers x and y. You are to find the number of good pairs of integers (a,b) such that l≤a,b≤r. Note that pairs (a,b) and (b,a) are considered different if a≠b.

The only line contains four integers l,r,x,y (1≤l≤r≤109, 1≤x≤y≤109).

In the only line print the only integer — the answer for the problem.

In the first example there are two suitable good pairs of integers (a,b): (1,2) and (2,1).

In the second example there are four suitable good pairs of integers (a,b): (1,12), (12,1),(3,4) and(4,3).

In the third example there are good pairs of integers, for example, (3,30), but none of them fits the condition l≤a,b≤rl≤a,b≤r.

题意就是给你一个范围（l,r）,让你找有多少个数对（a,b）满足a和b的最大公约数是x，最小公倍数是y

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<cstdlib>

#include<climits>

#include<functional>

#include<queue>

#include<vector>

#include<algorithm>

#define N 1000005

using namespace std;

long long prime[N+],len=,pd[N+]= {};

void shushu()

{

    pd[]=pd[]=;

    for(int i=; i<=N; i++)

    {

        if(pd[i]==)

        {

            prime[len++]=i;

        }

        for(int j=; j<len; j++)

        {

            if(i*prime[j]>=N)

                break;

            pd[i*prime[j]]=;

            if(i%prime[j]==)

                break;

        }

    }

}

long long l,r,x,y,team[],team1[]= {},team2[]= {},c1=,ans=;

long long ff(long long a,long long b);

void f(long long x,long long a,long long b)

{

    if(x==c1)

    {

        if(a>=l&&a<=r&&b>=l&&b<=r)

        {

            ans++;

        }

        return;

    }

    f(x+,a,b);

    if(team1[x]!=team2[x])

        f(x+,a/ff(team[x],team1[x])*ff(team[x],team2[x]),b/ff(team[x],team2[x])*ff(team[x],team1[x]));

}

long long ff(long long a,long long b)

{

    long long ans=;

    while(b>)

    {

        if(b%==)

        {

            ans*=a;

        }

        a*=a;

        b/=;

    }

    return ans;

}

int main()

{

    shushu();

    scanf("%I64d %I64d %I64d %I64d",&l,&r,&x,&y);

    if(y%x!=)

    {

        printf("");

        return ;

    }

    for(int i=; i<len; i++)

    {

        if(y%prime[i]==)

            team[c1++]=prime[i];

        while(y%prime[i]==)

        {

            team2[c1-]++;

            y/=prime[i];

        }

    }

    if(y>)

    {

        team[c1++]=y;

        team2[c1-]++;

    }

    for(int i=; i<c1; i++)

    {

        while(x%team[i]==)

        {

            team1[i]++;

            x/=team[i];

        }

    }

    long long a=,b=;

    for(int i=; i<c1; i++)

        a*=ff(team[i],team1[i]);

    for(int i=; i<c1; i++)

        b*=ff(team[i],team2[i]);

    f(,a,b);

    printf("%I64d",ans);

    return ;

}