[Problem Description] Input two positive integers X0, Y0 (2 ≤ x0 ≤ 100000, 2 ≤ y0 ≤ 1000000), and the number of p and q meet the following conditions are obtained. Conditions: 1, p, q is positive integer 2, require p, q with XO as the maximum number of conventions, with the least common multiple of YO. Try, meet all possible two positive integers of the conditions. [Sample] Enter: X0 = 3 y0 = 60 Output: 4 Description: (No output) The PQ at this time is, 3 6015 1212 1560 3, respectively, all possible two positive integers of the condition, 4 .
Knowledge preparation:
If the maximum number of conventions of P, Q is X0, then:
P% X0 = 0, q% x0 = 0
Suppose P1 = P / X0 Q1 = Q / X0
Perform the following derivation:
1. If p1 = q1, according to the definition of the maximum number of conventions, P1 = Q1 = 1, P = Q = X0, according to the least common number, P = Q = Y0, then X0 = Y0 = P = Q
2. If p1! = Q1, according to the definition of the maximum number of conventions, the P1 and Q1 have no other same factor, ie, P1, Q1.
3. According to the least common definition, Y0 = PQ / X0, and P1 = P / X0, Q1 = Q / X0, the following equation can be introduced: P1Q1 = Y0 / X0.
According to the above analysis, the following algorithms can be launched:
1. If Y0% X0! = 0, then P, Q does not exist.
2. If Y0 = X0, there is a set of p, q, and p = Q = X0 = Y0
3. Find data pairs that satisfy P1Q1 = Y0 / X0 and P1Q1 = Y0 / X0 and P1, Q1 are found between 1 ~ Y0 / X0.
The reference procedure is as follows:
#include
#include
Using namespace std;
Long X, Y, P, Q, I, S;
INT HZ (Long P, Long Q) // Judgment P, Q Mutual
{
LONG J;
For (j = 2; j <= p; j )
IF (p% j == 0 && q% J == 0)
Return 0;
Return 1;
}
int main ()
{
Freopen ("in.txt", "r", stdin;
Freopen ("Out.txt", "W", stdout);
While (CIN >> X >> Y)
{
IF (y% x! = 0)
COUT << 0 << endl;
Else IF (y == x) cout << 1 << endl;
Else
{
S = 0;
i = Y / x;
For (p = 1; P <= i; p )
For (q = 1; q <= i; q )
IF ((p * q == y / x) && Hz (p, q))
S ;
Cout << s << endl;
}
}
Return 0;
}
two. Improvement of algorithms
1. guess
According to the previous analysis: If the maximum number of conventions of P, Q is x, the minimum male number is Y, then the Q1 data is ok as long as the Look satisfies the product is Y / X and the p1, Q1 data is ok. Is this data on the number of data?
Guess: Y0 / X0 is set to be k, then the conditions of the conditions are met, Q is 2 ^ K, ie the number of neutron collection.
prove:
Suppose Y0 / X0 has K quality factor, Y0 / X0 = A1 * A1 * ... AK (AI is a magnet, the arithmetic basic theorem) should make P1 * Q1 = Y0 / X0, and P1, Q1, then P1, Q1 The same quality factor cannot be contained, so the total number of choices of P1 and Q1 is
How to count the quality factor of the integer S? The simplest method is linear lookup. Since then, it is accumulated. The first data that can be eliminated will inevitably, and after the cycle is excluded, the next data can be used as a quality factor.
The algorithm is as follows:
1. i = 2;
2. While (s% i! = 0) s ;
3. K ;
4. While (S% i == 0) s = S / I;
5. Continue to perform the statement 2.
The reference procedure is as follows:
#include
