https://www.luogu.com.cn/problem/P1029#ideP1029 [NOIP 2001 普及组] 最大公约数和最小公倍数问题题目描述输入两个正整数 x_0, y_0求出满足下列条件的 P, Q 的个数1. $P,Q$ 是正整数。2. 要求 P, Q 以 x_0 为最大公约数以 y_0 为最小公倍数。试求满足条件的所有可能的 P, Q 的个数。输入格式一行两个正整数 x_0, y_0。输出格式一行一个数表示求出满足条件的 $P, Q$ 的个数。## 输入输出样例 #1### 输入 #13 60### 输出 #14## 说明/提示$P,Q$ 有 $4$ 种1. $3, 60$。2. $15, 12$。3. $12, 15$。4. $60, 3$。对于 $100\%$ 的数据$2 \le x_0, y_0 \le {10}^5$。**【题目来源】**NOIP 2001 普及组第二题当然可以暴力循环解决问题这是暴力代码甚至还不完全对没有考虑到输入xy的情况。耗时你就看吧#includeiostreamusing namespace std;int maxgy(int a,int b)//返回最大公约数{if(b0)return a;else return maxgy(b,a%b);}int mingb(int a,int b,int gy){return a*b/gy;}int main(){int x0,y0;while(cinx0y0){ int count0;for(long long i2;i100000;i){for(long long ji;j100000;j){if(maxgy(i,j)x0 mingb(i,j,maxgy(i,j))y0)count2;}}coutcountendl;}}花了二十五分钟关键是能否理解这个数学关系首先如果想让pq满足x0是他们的最大公约数其最小公倍数又是y0先要知道一个条件两个数之积等于其最大公约数与最小公倍数之积即p*qx0*y0知道这个之后我们就可以只循环一次从1循环到sqrtx0*y0为什么我们在这个范围内选择一个i如果他满足 x0*y0%i0 那就说明i*jj是另一个数x0*y0即两个数之积等于其最大公约数与最小公倍数之积。但是现在的问题是我们既不知道x0是否是i和j的最大公约数也不知道y0是否是i和j的最小公倍数。而我们只需要求出任意一个我们假如可以知道x0是i和j的最大公约数那么根据i*jx0*y0就一定知道y0是i和j的最小公倍数因为两个数之积等于其最大公约数与最小公倍数之积。而给定两个数求最小公倍数也需要我们先求出最大公约数所以我们就将另一个条件设为i与j的最大公约数等于x0结合起来就是n%i0 maxgy(i,n/i)x0。为什么只需要判断到sqrtx0*y0就可以了因为这个ij是成对出现的即如果i*jx0*y0那么一定有j*ix0*y0每当我们找到一组数据直接让结果2即可而这个对称轴就是sqrtx0*y0当isqrtx0*y0时jisqrtx0*y0。同时i与j的最大公约数是i最小公倍数是i即ijx0y0所以如果输入的x0y0就会出现对称轴的情况此时count只需1而循环中默认2所以我们在输入x0y0时直接先将count-1就好了#includeiostream#includemath.husing namespace std;long long maxgy(long long a,long long b)//返回最大公约数{if(b0)return a;else return maxgy(b,a%b);}long long mingb(long long a,long long b,long long gy){return a*b/gy;}int main(){long long x0,y0;while(cinx0y0){ int count0;long long nx0*y0;//if(x0y0)count--;for(long long i1;isqrt(n);i){if(n%i0 maxgy(i,n/i)x0)count2;}coutcountendl;}}
洛谷P1029
https://www.luogu.com.cn/problem/P1029#ideP1029 [NOIP 2001 普及组] 最大公约数和最小公倍数问题题目描述输入两个正整数 x_0, y_0求出满足下列条件的 P, Q 的个数1. $P,Q$ 是正整数。2. 要求 P, Q 以 x_0 为最大公约数以 y_0 为最小公倍数。试求满足条件的所有可能的 P, Q 的个数。输入格式一行两个正整数 x_0, y_0。输出格式一行一个数表示求出满足条件的 $P, Q$ 的个数。## 输入输出样例 #1### 输入 #13 60### 输出 #14## 说明/提示$P,Q$ 有 $4$ 种1. $3, 60$。2. $15, 12$。3. $12, 15$。4. $60, 3$。对于 $100\%$ 的数据$2 \le x_0, y_0 \le {10}^5$。**【题目来源】**NOIP 2001 普及组第二题当然可以暴力循环解决问题这是暴力代码甚至还不完全对没有考虑到输入xy的情况。耗时你就看吧#includeiostreamusing namespace std;int maxgy(int a,int b)//返回最大公约数{if(b0)return a;else return maxgy(b,a%b);}int mingb(int a,int b,int gy){return a*b/gy;}int main(){int x0,y0;while(cinx0y0){ int count0;for(long long i2;i100000;i){for(long long ji;j100000;j){if(maxgy(i,j)x0 mingb(i,j,maxgy(i,j))y0)count2;}}coutcountendl;}}花了二十五分钟关键是能否理解这个数学关系首先如果想让pq满足x0是他们的最大公约数其最小公倍数又是y0先要知道一个条件两个数之积等于其最大公约数与最小公倍数之积即p*qx0*y0知道这个之后我们就可以只循环一次从1循环到sqrtx0*y0为什么我们在这个范围内选择一个i如果他满足 x0*y0%i0 那就说明i*jj是另一个数x0*y0即两个数之积等于其最大公约数与最小公倍数之积。但是现在的问题是我们既不知道x0是否是i和j的最大公约数也不知道y0是否是i和j的最小公倍数。而我们只需要求出任意一个我们假如可以知道x0是i和j的最大公约数那么根据i*jx0*y0就一定知道y0是i和j的最小公倍数因为两个数之积等于其最大公约数与最小公倍数之积。而给定两个数求最小公倍数也需要我们先求出最大公约数所以我们就将另一个条件设为i与j的最大公约数等于x0结合起来就是n%i0 maxgy(i,n/i)x0。为什么只需要判断到sqrtx0*y0就可以了因为这个ij是成对出现的即如果i*jx0*y0那么一定有j*ix0*y0每当我们找到一组数据直接让结果2即可而这个对称轴就是sqrtx0*y0当isqrtx0*y0时jisqrtx0*y0。同时i与j的最大公约数是i最小公倍数是i即ijx0y0所以如果输入的x0y0就会出现对称轴的情况此时count只需1而循环中默认2所以我们在输入x0y0时直接先将count-1就好了#includeiostream#includemath.husing namespace std;long long maxgy(long long a,long long b)//返回最大公约数{if(b0)return a;else return maxgy(b,a%b);}long long mingb(long long a,long long b,long long gy){return a*b/gy;}int main(){long long x0,y0;while(cinx0y0){ int count0;long long nx0*y0;//if(x0y0)count--;for(long long i1;isqrt(n);i){if(n%i0 maxgy(i,n/i)x0)count2;}coutcountendl;}}
