网站是可以做的吗品牌免费网站建设

网站是可以做的吗,品牌免费网站建设,百度指数需求图谱,公司门户网站建设题目描述 输入两个正整数 x0​,y0​#xff0c;求出满足下列条件的 P,Q 的个数#xff1a; P,Q 是正整数。 要求 P,Q 以 x0​ 为最大公约数#xff0c;以 y0​ 为最小公倍数。 试求#xff1a;满足条件的所有可能的 P,Q 的个数。 输入格式 一行两个正整数 x0​,y0​。…题目描述输入两个正整数 x0​,y0​求出满足下列条件的 P,Q 的个数P,Q 是正整数。要求 P,Q 以 x0​ 为最大公约数以 y0​ 为最小公倍数。试求满足条件的所有可能的 P,Q 的个数。输入格式一行两个正整数 x0​,y0​。输出格式一行一个数表示求出满足条件的 P,Q 的个数。输入3 60输出4说明/提示P,Q 有 4 种3,60。15,12。12,15。60,3。对于 100% 的数据2≤x0​,y0​≤10^5。#includestdio.h int gcd(int a,int b)//判断最小公倍数 { while(b!0){ int ta%b; ab; bt; } return a;//a即为最小公倍数 } int main() { int x,y; scanf(%d%d,x,y); if(y%x!0){//最小公倍数一定是最大公约数的倍数如果不是则没有解直接打印出0退出。 printf(0\n); return 0; } int ny/x;//最小公倍数的作用只是和最大公因数找出p的范围。 int count0; int p; for(p1;p*pn;p){ if(n%p0){//虽然我们明确np*q,但是并不能确定1~sqrt(n)内的数除以p等于q. int qn/p;//到这一步只是求得了p和q两个因子但二者不一定是互质的所以后面还要判断是否互质。只有是互质的才能得出x是最大公因数。 if((gcd(p,q))1){//判断p和q是否互质 if(pq){ count;//说明在计算a和b这两个数的时候得到的a和b是相等的只有一个结果所以只需要加1. }else{ count2;//说明得到的a和b是不相等的 } } } } printf(%d\n,count); return 0; }详细解析上述代码逻辑数学逻辑挺强1.ny/x;最大公约数是x最小公倍数是y设这两个数为a,b,p和q为去掉最大公约数后各自独有的部分。而ax*p,bx*q.其中p和q是互质的正整数即二者除了1没有其他公因数。因为p和q还有大于1的公因数则x就不是最大公约数了。解析上述假设有a12,b18,他们的最大公约数是6即x6。可以写成126*2,186*3,即a12x*p(2),b18x*q(3).一般化即为ax*p,bx*q。为什么p和q必须互质如果a4010*4,b6010*6,则p和q不互质则10不是二者的最大公约数二者的最大公约数其实是20.所以如果p和q不互质则x并不是最大公因数。2.为什么要定义ny/xa*b(x*p)*(x*q)x^2*p*q,所以a*b/xx*p*q,即最小公倍数ya*b/xx*p*q,所以y/xp*q.所以令ny/x,则np*q.定义ny/x是因为n通常比y小很多只需要对n进行因数分解并检查每对因数是否互质避免了直接枚举a和b大量结合。3.实例演示假设x3,y60.计算ny/x60/320;找到所有互质的整数对p,q)使得p*q20。20的因数对(1, 20)、(2, 10)、(4, 5)、(5, 4)、(10, 2)、(20, 1)。 其中互质的对是(1, 20) 和 (4, 5)注意 (5, 4) 与 (4, 5) 视为同一对的不同顺序但通常只计算一次因为 a 和 b 的顺序不影响数对。对应的 (a, b) 为(3*1, 3*20) (3, 60)。(3*4, 3*5) (12, 15)所以有两组解。(由题意得x3,p和q互质只有p1,q20,所以ax*p,bx*q)这是通过p和q计算的a和b两个数4.为什么循环是p*pn:我们要通过循环找到所有的p,q)整数对使得p*qnp和q互质。为什么用 p * p n 而不是 p n思想实验假设 n 100· 如果 p 1那么 q 100/1 100· 如果 p 2那么 q 100/2 50· 如果 p 4那么 q 100/4 25· 如果 p 5那么 q 100/5 20· 如果 p 10那么 q 100/10 10· 如果 p 20那么 q 100/20 5由上述可得当psqrt(n)时相当于p和q又发生交换。我们要得到的p和q其实是psqrt(n)时的值。这样可以减少遍历因为二者一样的只需要计数加2即可。通过上述方法求出来的p和q并不是满足条件的两个数而是因子通过这两个因子求得的a和b才是最终的满足条件的两个数即为下面的3,60。15,12。12,15。60,3。