当前位置：首页 > news >正文

有哪些做问卷调查挣钱的网站优化设计三年级上册答案

news 2025/8/28 9:49:18

有哪些做问卷调查挣钱的网站,优化设计三年级上册答案,商业网站技术,做seo排名好的网站题目描述： 输入两个正整数 x0,y0，求出满足下列条件的 P,Q 的个数： P,Q 是正整数。要求P,Q 以 x0 为最大公约数，以 y0 为最小公倍数。试求：满足条件的所有可能的 P,Q 的个数。输入格式一行两个正整数…

题目描述：

输入两个正整数 x0,y0，求出满足下列条件的 P,Q 的个数：

P,Q 是正整数。
要求P,Q 以 x0 为最大公约数，以 y0 为最小公倍数。

试求：满足条件的所有可能的 P,Q 的个数。

输入格式

一行两个正整数 x0,y0。

输出格式

一行一个数，表示求出满足条件的 P,Q 的个数。

输入输出样例

输入 #1

3 60

输出 #1

说明/提示

P,Q 有 4 种：

3,60。
15,12。
12,15。
60,3。

对于 100% 的数据，2≤x0,y0≤10^5。

【题目来源】

P1029 [NOIP2001 普及组] 最大公约数和最小公倍数问题

思路及部分代码：

1. 求出最大最小

//返回最大值或者最小值
//根据 d 的值返回最大或者最小
int max_min(int a, int b,int d){int max, min;if(a >= b){max = a;min = b;}else{max = b;min = a;}if(d == 0) return min;else return max;
}

2. 欧几里得算法求最大公约数

原本想遍历出结果，但时间复杂度太高，所以学习了一下欧几里得算法。

欧几里得算法（辗转相除法）：其基本思想是用较大的数除以较小的数，然后用较小的数去除余数，再用新的余数去除小的数，如此反复，直到余数为零为止，此时除数就是最大公约数。

//求出最大公约数
/*
欧几里得算法（辗转相除法），其基本思想是用较大的数除以较小的数，
然后用较小的数去除余数，再用新的余数去除小的数，如此反复，
直到余数为零为止，此时除数就是最大公约数。具体步骤如下：
*/
int Common_divisor_max(int x, int y){int max = max_min(x,y,1);   //求出最大数int c_n = x+y-max;  //除数int c = max % c_n;    //被除数while(c != 0){int di = c; //除数被除数交换c = c_n;c_n = di;c = c % c_n;}return c_n;/*for(int i = max;i >= 1;i--){if(x%i == 0 && y%i == 0){   //满足最大公约数return i;}}*///return 0;
}

3. 最小公倍数

也是考虑到时间复杂度问题，把遍历改成利用公约数求公倍数。

关系：两个数的乘积等于它们的最大公约数与最小公倍数的乘积。

//求出最小公倍数
int Common_multiple_min(int x,int y,int yue){return x*y/yue;/*int max = max_min(x,y,1);   //求出最大数for(int i = max; i<= x*y;i = i + yue){if(i%x == 0 && i%y == 0){return i;}}*///return -1;  //错误
}

4. 思路遍历

a. 我们知道在P/Q是在输入的x,y中，所以这里给出了一个范围。

b. 但在实际情况下我们所P/Q的遍历有太多的无用值，浪费我们的计算时间。

c. 我们由最小公倍数中的关系可得一个判定方式。

d. 再在我们的函数中，可以根据最大公约数与X再进行一次判定，最后再与Y判定。

P = max_min(x,y, 0);
Q = max_min(x,y, 1);int cnt = 0;    //计数满足要求的Q P
for(int i = P; i <= Q; i = i + x){//遍历方式求解，时间复杂度太高for(int j = Q; j >= P; j= j - x){if(j*i == x*y){int yue = Common_divisor_max(i, j);if(yue != x)   ;//跳过else if(Common_multiple_min(i,j, yue) == y){cnt++;//printf("P = %d   Q = %d \r\n", i,j);}}  }
}

总代码：

#include <stdio.h>//返回最大值或者最小值
int max_min(int a, int b,int d){int max, min;if(a >= b){max = a;min = b;}else{max = b;min = a;}if(d == 0) return min;else return max;
}//求出最大公约数
/*
欧几里得算法（辗转相除法），其基本思想是用较大的数除以较小的数，
然后用较小的数去除余数，再用新的余数去除小的数，如此反复，
直到余数为零为止，此时除数就是最大公约数。具体步骤如下：
*/
int Common_divisor_max(int x, int y){int max = max_min(x,y,1);   //求出最大数int c_n = x+y-max;  //除数int c = max % c_n;    //被除数while(c != 0){int di = c; //除数被除数交换c = c_n;c_n = di;c = c % c_n;}return c_n;/*for(int i = max;i >= 1;i--){if(x%i == 0 && y%i == 0){   //满足最大公约数return i;}}*///return 0;
}//求出最小公倍数
int Common_multiple_min(int x,int y,int yue){return x*y/yue;/*int max = max_min(x,y,1);   //求出最大数for(int i = max; i<= x*y;i = i + yue){if(i%x == 0 && i%y == 0){return i;}}*///return -1;  //错误
}int main (){int x,y;scanf("%d %d",&x, &y);int P,Q;P = max_min(x,y, 0);Q = max_min(x,y, 1);int cnt = 0;    //计数满足要求的Q Pfor(int i = P; i <= Q; i = i + x){//遍历方式求解，时间复杂度太高for(int j = Q; j >= P; j= j - x){if(j*i == x*y){int yue = Common_divisor_max(i, j);if(yue != x)   ;//跳过else if(Common_multiple_min(i,j, yue) == y){cnt++;//printf("P = %d   Q = %d \r\n", i,j);}}}}printf("%d\r\n",cnt);return 0;
}