CF992B Nastya Studies Informatics 数学（因子）暴力求解第三道-白红宇

CF992B Nastya Studies Informatics 数学（因子）暴力求解第三道

阅读量：6815 次

发布时间：2019-06-26

本文共 2399 字，大约阅读时间需要 7 分钟。

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 of a and b, and LCM(a, b) denotes the 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.

Input

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

Output

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

Examples

input

Copy

1 2 1 2

output

Copy

input

Copy

1 12 1 12

output

Copy

input

Copy

50 100 3 30

output

Copy

Note

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 ≤ r.

给你四个数l，r，a，b，问在l到r的范围内有多少对数（两个数不能相同，顺序可以不同）满足gcd(x,y)=a,lcm(x,y)=b

枚举b的因子个数，再看这些因子每每两个的最大公约数是否等于a，等于a满足条件情况加一

#include #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #define debug(a) cout << #a << " " << a << endlusing namespace std;const int maxn = 1e3 + 10;typedef long long ll;ll gcd( ll p, ll q ) { if( p == 0 ) { return q; } if( q == 0 ) { return p; } return gcd( q, p%q );}int main(){ std::ios::sync_with_stdio(false); ll l, r, a, b; //cout << gcd( 16, 4 ) << endl; while( cin >> l >> r >> a >> b ) { ll num = 0; vector
                
                  e; for( ll i = 1; i * i <= b; i ++ ) { if( b % i == 0 ) { e.push_back(i); if( i != b/i ) { e.push_back(b/i); } //debug(i),debug(b/i); } } for( ll i = 0; i < e.size(); i ++ ) { for( ll j = 0; j < e.size(); j ++ ) { if( gcd( e[i], e[j] ) == a && e[i] * e[j] == a * b && e[i] >= l && e[i] <= r && e[j] >= l && e[j] <= r ) { num ++; } } } cout << num << endl; } return 0;}

转载于:https://www.cnblogs.com/l609929321/p/9210618.html

你可能感兴趣的文章

nginx配置让任何文件在浏览器中显示文本text/plain