Summary:
1. If LCM (b, x) = = d, (the least common multiple of b, x = = d), you should know that B and X are divisors of d.
2. When b and x are divisors of d, the prime factors in b and x exist in the least common multiple of d.
3. Number of divisors: the upper bound of the number of divisors of n is sqrt(n), that is, there are at most sqrt(n) divisors, but in fact, if it is averaged from 1 to N, there are only (log n) divisors of each number.
4. Within 1e9, the maximum number of divisors is 1536
5. From 3 and 4, we can know that if there are multiple groups of test data and find the divisor of N, in fact, we can preprocess sqrt(max(n)). According to the requirements of the topic, all the prime numbers of sqrt(n) under the maximum value of N are screened out
Then, each quality factor and index corresponding to the current n are directly screened out with the preprocessed prime number {of n. (in fact, according to the previous topic of inverse primes, in fact, the prime factor of n will not exceed 11 Inverse prime problem solution)
After sifting out the corresponding quality factor and index, calculate each divisor directly through dfs() and save it.
6. At the same time, the relationship between the prime factor and the least common multiple is often used to solve the maximum common divisor and the least common multiple. (the previous problems of maximum common divisor and minimum common multiple are solved in this way). Problem solving link: https://blog.csdn.net/qq_49120553/article/details/119078625?spm=1001.2014.3001.5502
If the prime factor of a is decomposed into (x1 ^ p1) * (x2 ^ p2) * (x3 ^ p3)
The prime factor of b is decomposed into (x1 ^ p4) * (x5 ^ p5) * (x6 ^ p6)
Prime factor a can be added: (x1 ^ P1) * (x2 ^ P2) * (X3 ^ P3) * (x5 ^ 0) * (x6 ^ 0)
b:(x1 ^ p4) * (x5 ^ p5) * (x6 ^ p6)* (x2 ^ 0) * (x3 ^ 0)
Then the maximum common divisor of a and B is: (x1 ^ min (P1, P4)) * (x2 ^ min (P2, 0)) * (X3 ^ min (p3,0)) * (x5 ^ min (0, P5)) * (x6 ^ min (0.p6))
a. The least common multiple of B is: (x1 ^ max (P1, P4)) * (x2 ^ max (P2, 0)) * (X3 ^ max (p3,0)) * (x5 ^ max (0, P5)) * (x6 ^ max (0.p6))
Title Link: https://ac.nowcoder.com/acm/problem/16610
Title:
Title Description
Dr. Hanks is a well-known expert in the field of BT (bio Tech), and his son's name is Hankson. Now, Hankson, who just came home from school, is thinking about an interesting question.
In class today, the teacher explained how to find the maximum common divisor and minimum common multiple of two positive integers c1 and c2. Now Hankson thinks that he has mastered these knowledge skillfully. He begins to think about an "inverse problem" of problems such as "seeking common divisor" and "seeking common multiple". This problem is as follows: if the positive integers A0, A1, B0 and B1 are known, let an unknown positive integer x satisfy:
1. The greatest common divisor of x and a0 is a1;
2. The least common multiple of x and b0 is b1.
Hankson's "inverse problem" is to find the positive integer x satisfying the condition. But after a little thought, he found that such an X is not unique, or even may not exist. Therefore, he began to consider how to solve the number of X satisfying the condition. Please help him solve the problem by programming.
Enter Description:
The first line is a positive integer n, indicating that there are n groups of input data. The next N lines are a set of input data for each line, which are four positive integers a0, a1, b0 and b1, separated by a space between each two integers. The input data ensures that a0 can be divided by a1 and b1 can be divided by b0.
Output Description:
For each group of data: if there is no such x, please output 0; If there is such an x, please output the number of x satisfying the condition;
Example 1
input
Copy 2 41 1 96 288 95 1 37 1776
2 41 1 96 288 95 1 37 1776
output
Copy 6 2
6 2
explain
The first group of input data, x, can be 9, 18, 36, 72, 144, 288, a total of 6. The second group of input data, x can be 48, 1776, a total of 2.
remarks:
For 50% of the data, 1 ≤ a0, b1, b0, b1 ≤ 10000 and n ≤ 100 are guaranteed.
For 100% data, it is guaranteed that 1 ≤ a0, b1, b0, b1 ≤ 2000000000 and n ≤ 2000.
Analysis 1:
From the conclusion, lcm(x,b0) == b1, then x is the divisor of b1.
Then we can directly find all divisors of b1, and then judge whether this divisor x satisfies our condition (GCD (x, A0) = = A1 & & LCM (x, B0) = = b1)
If the conditions are met, the statistical value total + +. Finally output.
However, it should be noted that if the trial division method is directly used to determine whether it is a divisor, the time complexity will become n*sqrt(b1) * log b1 Will time out.
So we need to use another technique in our summary to find the divisor of a number. First, screen out the prime number in the maximum sqrt(n). (like the previous sieve quality factor, sieve sqrt(n) first, and the only value greater than sqrt(n) is left). Then, through the screened prime number, the prime number satisfying the condition and its exponent in sqrt(n) are screened out.
Finally, all the corresponding divisors can be solved by dfs(). (reduce non divisible cases)
Code implementation:
90 Code:
# include <iostream>
using namespace std;
int gcd(int a , int b)
{
return b ? gcd(b,a % b) : a;
}
int main()
{
int loop;
scanf("%d",&loop);
while(loop--)
{
int a0,a1,b0,b1;
scanf("%d %d %d %d",&a0,&a1,&b0,&b1);
int cnt = 0;
for(int i = 1 ; i <= b1 / i ; i++)
{
if(b1 % i == 0)
{
int temp1 = i;
if(gcd(temp1,a0) == a1 && (long long)gcd(temp1,b0) * b1 == (long long)temp1 * b0)
{
cnt++;
}
if(b1 / i != i)
{
temp1 = b1 / i;
}
if(gcd(temp1,a0) == a1 && gcd(temp1,b0) * b1 == temp1 * b0)
{
cnt++;
}
}
}
printf("%d\n",cnt);
}
return 0;
}ac Code:
# include <iostream>
# include <vector>
using namespace std;
const int N = 2e5 + 10;
int prim[N],cnt;
bool choose[N];
typedef pair<int,int> PII;
vector<PII> p;
int t; // Number of statistical divisors
int yueshu[N];
int gcd(int a , int b)
{
return b ? gcd(b,a % b) : a;
}
void get_prim(int n)
{
for(int i = 2 ; i <= n ; i++)
{
if(!choose[i])
{
prim[++cnt] = i;
}
for(int j = 1 ; prim[j] <= n / i ; j++)
{
choose[i * prim[j]] = true;
if(i % prim[j] == 0)
{
break;
}
}
}
}
void dfs(int u , int i)
{
if(i == p.size())
{
yueshu[++t] = u;
return;
}
for(int j = 0 ; j <= p[i].second ; j++)
{
dfs(u, i + 1);
u = u * p[i].first; // Finally, it will multiply u one more time, but it doesn't affect it, because the last u is useless
}
}
int main()
{
get_prim(N); // Pretreat the prime number of the front sqrt(2e9) sieve.
int loop;
scanf("%d",&loop);
while(loop--)
{
p.clear();
t = 0;
int a0,a1,b0,b1;
scanf("%d %d %d %d",&a0,&a1,&b0,&b1);
int d = b1;
//To find the divisor of b1, first find the prime number corresponding to b1 and its corresponding prime number
for(int i = 1 ; prim[i] <= d / prim[i] ; i++) // Just screen out the value corresponding to the previous sqrt(b1), and the last value is greater than sqrt(b1)
{
if(d % prim[i] == 0)
{
int time = 0;
while(d % prim[i] == 0)
{
time++;
d /= prim[i];
}
p.push_back({prim[i],time});
}
}
if(d > 1) //Finally, the remaining value is greater than sqrt(b1)
{
p.push_back({d,1});
}
//In the above step, all the primes and exponents of b1 are rounded out. Next, find the corresponding divisor
dfs(1,0); // dfs(u,i) u represents the current value, and i represents the index
//dfs() above sorts out all divisors
int count = 0; // Find the number of conditions
for(int i = 1 ; i <= t ; i++)
{
int x = yueshu[i];
if (gcd(x, a0) == a1 && (long long)x * b0 / gcd(x, b0) == b1)
{
count++ ;
}
}
printf("%d\n",count);
}
return 0;
}Analysis 2:
Another way is to use the relationship between gcd() and lcm() and the prime factor.
From our analysis, we know that x is the divisor of d1. So all the prime factors in X must be in d1.
Therefore, we calculate the quality factors of d1 and their exponents, as well as the quality factors of d1 and their corresponding exponents of A0 and A1.
According to the relationship between gcd() and lcm() and quality factor, the corresponding relationship is summarized.
Each of the corresponding unsolved cases is the corresponding a,b,c,d. the value is illegal, and the corresponding x cannot be found.
The corresponding value is 0
If there is no solution, then the corresponding value of each d1 corresponding to the prime factor is solved by the multiplication principle to get the final answer.
# include <iostream>
# include <vector>
using namespace std;
const int N = 2e5 + 10;
int prim[N],cnt;
bool choose[N];
void get_prim(int n)
{
for(int i = 2 ; i <= n ; i++)
{
if(!choose[i])
{
prim[++cnt] = i;
}
for(int j = 1 ; prim[j] <= n / i ; j++)
{
choose[i * prim[j]] = true;
if(i % prim[j] == 0)
{
break;
}
}
}
}
int main()
{
get_prim(N); // Pretreat the prime number of the front sqrt(2e9) sieve.
int loop;
scanf("%d",&loop);
while(loop--)
{
int a0,a1,b0,b1;
scanf("%d %d %d %d",&a0,&a1,&b0,&b1);
int a = a0;
int c = a1;
int b = b0;
int d = b1;
int count = 1;
bool flag = true;
for(int i = 1 ; prim[i] <= d / prim[i] ; i++)
{
int ma = 0,mc = 0,mb = 0,md = 0;
if(d % prim[i] == 0)
{
while(a % prim[i] == 0)
{
ma++;
a /= prim[i];
}
while(c % prim[i] == 0)
{
mc++;
c /= prim[i];
}
while(b % prim[i] == 0)
{
mb++;
b /= prim[i];
}
while(d % prim[i] == 0)
{
md++;
d /= prim[i];
}
if(ma == mc && mb == md && mc <= md)
{
count *= (md - mc + 1);
}
else if(ma > mc && mb < md && mc == md)
{
continue;
}
else if(ma > mc && mb == md && mc <= md)
{
continue;
}
else if(ma == mc && mb < md && mc <= md)
{
continue;
}
else
{
flag = false;
break;
}
}
}
if(flag && d > 1)
{
int ma = 0,mc = 0,mb = 0,md = 1;
while(a % d == 0)
{
ma++;
a /= d;
}
while(c % d == 0)
{
mc++;
c /= d;
}
while(b % d == 0)
{
mb++;
b /= d;
}
if(ma == mc && mb == md && mc <= md)
{
count *= (md - mc + 1);
}
else if(ma > mc && mb < md && mc == md)
{
count *= 1;
}
else if(ma > mc && mb == md && mc <= md)
{
count *= 1;
}
else if(ma == mc && mb < md && mc <= md)
{
count *= 1;
}
else
{
flag = false;
}
}
if(flag)
{
printf("%d\n",count);
}
else
{
printf("0\n");
}
}
return 0;
}