Solution to the problem of the greatest common divisor and the least common multiple of Luogu p1029

Topic link ：​ ​https://www.luogu.com.cn/problem/P1029​​

Title Description

Input \(2\) A positive integer \(x_0,y_0(2 \le x_0 \lt 100000,2 \le y_0 \le 1000000)\) , If the following conditions are satisfied \(P,Q\) The number of .
Conditions ：

1. \(P,Q\) It's a positive integer. ;
2. requirement \(P,Q\) With \(x_0\) For the greatest common divisor , With \(y_0\) Is the minimum common multiple .

Try to ask for ： All possible that meet the conditions \(2\) The number of positive integers .

Input format

\(2\) A positive integer \(x_0,y_0\)

Output format

\(1\) Number , It means to find out if the condition is satisfied \(P,Q\) The number of

Problem analysis

Although this topic is named 《 The problem of maximum common divisor and minimum common multiple 》 And it can be done by the solution of the greatest common divisor and the least common multiple , But this problem can also be solved by decomposing the prime factor .

There are two ways to solve this problem ：

solution 1 GCD+ enumeration

This GCD In fact, that is “ greatest common divisor ”（greatest common divisor） Abbreviation .

First , For the two numbers given to us \(x_0\) and \(y_0\) , If \(x_0\) Not divisible \(y_0\) , So the answer must be \(0\) individual .

Otherwise , We are from \(x_0\) To \(y_0\) Enumerate all the way \(P\) , according to \(P\) We can get \(Q\) by \(x_0 \times y_0 / P\) .
Now of course \(Q\) Not necessarily legal ,
\(Q\) Legally if and only if \(GCD(P,Q) = x_0\) .

Then count the time when \(P\) In the interval \([x0,y0]\) How many legal \(Q\) that will do .

The implementation code is as follows ：

Log in and copy

      
      

       
       #include <bits/stdc++.h>
       
       
using namespace std;
       
       
long long x, y;
       
       

       
       
long long gcd(long long a, long long b) {
       
       
    if (b == 0) return a;
       
       
    return gcd(b, a%b);
       
       
}
       
       

       
       
int main() {
       
       
    cin >> x >> y;
       
       
    if (y % x) puts("0");
       
       
    else {
       
       
        int cnt = 0;
       
       
        for (long long p = x; p <= y; p ++) {
       
       
            if (y % p || p % x) continue; // P Must be able to be x0 to be divisible by , At the same time, it can divide y0
       
       
            long long q = x * y / p;
       
       
            if (gcd(p, q) == x) cnt ++;
       
       
        }
       
       
        cout << cnt << endl;
       
       
    }
       
       
    return 0;
       
       
}
      
      
      
      

       
       
1.
       
       
2.
       
       
3.
       
       
4.
       
       
5.
       
       
6.
       
       
7.
       
       
8.
       
       
9.
       
       
10.
       
       
11.
       
       
12.
       
       
13.
       
       
14.
       
       
15.
       
       
16.
       
       
17.
       
       
18.
       
       
19.
       
       
20.
       
       
21.
       
       
22.
       
       
23.
      
      

However, there is a faster solution to this problem , That's what I'm going to talk about next ：

solution 2 Decomposing prime factor

We use “ Decomposing prime factor ” To solve this problem .

First , If \(x0\) Not divisible \(y0\) , Then the answer must be \(0\) , Direct output \(0\) that will do .

secondly , We make \(n = y_0 / x_0\) , Then on \(n\) Do prime factor decomposition , Suppose to be right \(n\) The expression for prime factor decomposition is ：
\(n = a_1^{b_1} \times a_2^{b_2} \times \dots \times a_m^{b_m}\)
So we know that , For any one of them \(a_i\) , It either goes to \(P\) , Or return to \(Q\) , There can be no \(1\) individual \(a_i\) come together \(P\) , And another one. \(a_i\) come together \(Q\) （ Because then their greatest common divisor becomes \(x0 \times a_i\)） , So for this \(m\) individual \(a_i\) , They either all go to \(P\) , Or they all go to \(Q\) , So the total number of schemes is \(2^m\) .
The implementation code is as follows （ I use \(cnt\) To represent the number of different prime factors ）：

Log in and copy

      
      

       
       #include <bits/stdc++.h>
       
       
using namespace std;
       
       
int x, y, n, m;
       
       

       
       
int main() {
       
       
    cin >> x >> y;
       
       
    if (y % x) puts("0");
       
       
    else {
       
       
        n = y / x;
       
       
        int a = sqrt(n);    //  take a square root 
       
       
        for (int i = 2; i <= a; i ++) {
       
       
            if (n % i == 0) {
       
       
                m ++;
       
       
                while (n % i == 0) n /= i;
       
       
            }
       
       
        }
       
       
        if (n > 1) m ++;
       
       
        cout << (1<<m) << endl;
       
       
    }
       
       
    return 0;
       
       
}
      
      
      
      

       
       
1.
       
       
2.
       
       
3.
       
       
4.
       
       
5.
       
       
6.
       
       
7.
       
       
8.
       
       
9.
       
       
10.
       
       
11.
       
       
12.
       
       
13.
       
       
14.
       
       
15.
       
       
16.
       
       
17.
       
       
18.
       
       
19.
       
       
20.
       
       
21.
      
      

Students who have learned bit operation should know , In code \(1<<m\) In fact, it means \(2^m\) , And that's our answer .