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

最大公约数和最小公倍数问题

http://218.5.5.242:9018/JudgeOnline/problem.php?id=1111

时间限制: 1 Sec

内存限制: 128 MB

题目描述

输入二个正整数x0,y0(2<=x0<100000,2<=y0<=1000000),求出满足下列条件的P,Q的个数。

条件:

1、P，Q是正整数

2、要求P，Q以x0为最大公约数，以y0为最小公倍数。

试求:满足条件的所有可能的两个正整数的个数。

样例

输入:x0=3 yo=60

输出:4

说明(不用输出)此时的 P Q 分别为:

　 3 60

15 12

12 15

60 3

所以:满足条件的所有可能的两个正整数的个数共4种.

输入

输入只有一行，为两个正整数x0和y0。

输出

输出只有一行，为满足条件的所有可能的两个正整数的个数。

样例输入

3 60

样例输出

来源

NOIP2001普及组

此题较UVa 10892（点击打开题解）更为简单。

完整代码：

/*0ms,964KB*/

#include<cstdio>

int main()
{
    long long m, n, nn, ans, i, count;
    scanf("%lld%lld", &m, &n);
    if (n % m) putchar('0');///注意特判
    else
    {
        n /= m;
        ans = 1;
        for (i = 2; i * i <= n; i += 2)///不用求素数，因为范围很小(注意n在不断减小)
        {
            if (n % i == 0)
            {
                count = 0;
                while (n % i == 0)
                {
                    n /= i;
                    ++count;
                }
                ans <<= 1;
            }
            if (i == 2)
                --i;///小技巧
        }
        if (n > 1) ans <<= 1;
        printf("%lld", ans);
    }
    return 0;
}

查看本栏目更多精彩内容：http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/

以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索问题
，题目
，整数
， noip阅读程序
，限制
，最大公约数
最小公倍数
noip2016普及组复赛、noip2015普及组复赛、noip2016普及组初赛、noip2013普及组复赛、noip2011普及组复赛，以便于您获取更多的相关知识。

时间： 2024-10-15 04:12:58

NOIP2001普及组最大公约数和最小公倍数问题的相关文章

Java求最大公约数与最小公倍数

如果数a能被数b整除,a就叫做b的倍数,b就叫做作a的约数．约数和倍数都表示一个数与另一个数的关系,不能单独存在．如只能说16是某数的倍数,2是某数的约数,而不能孤立地说16是倍数,2是约数． "倍"与"倍数"是不同的两个概念,"倍"是指两个数相除的商,它可以是整数.小数或者分数．"倍数"只是在数的整除范围内,相对于"约数"而言的一个数字概念,表示的是能被某一个自然数整除的数,它必须是一个自然数． (1)

输入两个正整数m和n并求其最大公约数和最小公倍数

查看全套"c语言习题集" 题目: 输入两个正整数m和n,求其最大公约数和最小公倍数. 1.程序分析:利用辗除法. 2.程序源代码: #include "stdio.h"#include "conio.h"main(){ int a,b,num1,num2,temp; printf("please input two numbers:\n"); scanf("%d,%d",&num1,&num

C++求二个数的最大公约数与最小公倍数实例

1.求二个数的最大公约数: #include <iostream.h> int maxye(int a,int b) { int temp; while(a%b) { temp=b; b=a%b; a=temp; } return b; } void main() { int aa,bb; cout<<"请输入第一个数:"; cin>>aa; cout<<"\n请输入第二个数:"; cin>>bb; cou

冒泡排序算法递归算法，求n的阶乘求最大公约数和最小公倍数 java分解质因数

1. /** 2. * 冒泡排序算法 3. */ 4. public class BubbleSort { 5. public static void sort(int[] values) { 6. int temp; 7. for (int i = 0; i < values.length; ++i) { 8. for (int j = 0; j <

更相损减法和辗转相除法求最大公约数和最小公倍数（C语言）

假设有两个数a和b,求a,b的最大公约数和最小公倍数实际上是一个问题,得出这两个数的最大公约数就可以算出它们的最小公倍数. 最小公倍数的公式是 a*b/m m为最大公约数因为 a=m*i; b=m*j; 最小公倍数为 m*i*j 那么,下面就开始计算a和b的最大公约数. 更相损减法: <九章算術·方田>作分數約簡時,提到求最大公因數方法:反覆把兩數的較大者減去較小者,直至兩數相等,這數就是最大公因數.這方法除了把除法換作減法外,與輾轉相除法完全相同.例如書中求91和49的最大公因數: 91

c++-从键盘上输入两个正整数，输出它们的最大公约数和最小公倍数用C++实现

问题描述从键盘上输入两个正整数,输出它们的最大公约数和最小公倍数用C++实现用C++实现,一早要交作业,急用C++实现,一早要交作业,急用C++实现,一早要交作业,急用C++实现,一早要交作业,急用C++实现,一早要交作业,急用C++实现,一早要交作业,急用C++实现,一早要交作业,急用C++实现,一早要交作业,急用C++实现,一早要交作业,急用C++实现,一早要交作业,急用C++实现,一早要交作业,急用C++实现,一早要交作业,急用C++实现,一早要交作业,急解决方案 http://ww

c语言-C语言用函数求最大公约数和最小公倍数，看不出错在哪，代码如下

问题描述 C语言用函数求最大公约数和最小公倍数,看不出错在哪,代码如下 #include int maxnumber(int x,int y) { int a=0; a=x%y; while(a!=0) { a=x%y; x=y; y=a; } return y; } int minnumber(int x,int y) { int z; z=(x*y)/maxnumber(x,y); return z; } void main() { int maxnumber(int x,int y); i

c-输入两个正整数m和n，求其最大公约数和最小公倍数。

问题描述输入两个正整数m和n,求其最大公约数和最小公倍数. 输入两个正整数m和n,求其最大公约数和最小公倍数. 解决方案 #include "stdio.h" #include "conio.h" main() { int a,b,num1,num2,temp; printf("please input two numbers: "); scanf("%d,%d",&num1,&num2); if(num1&

C语言OJ项目参考(1047) 最大公约数和最小公倍数

1047: 求两个整数的最大公约数和最小公倍数 Description 写两个函数,分别求两个整数的最大公约数和最小公倍数,用主函数调用这两个函数,并输出结果两个整数由键盘输入. Input 两个数 Output 最大公约数最小公倍数 Sample Input 6 15 Sample Output 3 30 HINT 主函数已给定如下,提交时不需要包含下述主函数 /* C代码 */ int main() { int n,m,gys,gbs; int gcd(int a, int b); int

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

NOIP2001普及组 最大公约数和最小公倍数问题的相关文章

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

NOIP2001普及组最大公约数和最小公倍数问题的相关文章