[NOIP普及组2001]最大公约数和最小公倍数问题

目录

• 链接
  • 博客链接
  • 题目链接
• 题目内容
  • 题目描述
  • 格式
    • 输入
    • 输出
• 数据
  • 样例
    • 输入
    • 输出
    • 说明

题目名称：最大公约数和最小公倍数问题

来源：2001年NOIP普及组

链接

博客链接

• CSDN
• 洛谷博客
• 洛谷题解

题目链接

• Vijos
• 洛谷(P1029)
• 入门OJ(1172)

题目内容

题目描述

输入二个正整数\(x_0,y_0(2\leq x_0\leq100000，2\leq y_0\leq1000000)\)，求出满足下列条件的\(P、Q\)的个数。
条件:

1. \(P、Q\)是正整数
2. 要求\(P、Q\)以\(x_0\)为最大公约数，以\(y_0\)为最小公倍数。

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

格式

输入

\(2\)个正整数\(x_0\),\(y_0\)

输出

\(1\)个数，表示求出满足条件的\(P\),\(Q\)的个数

数据

样例

输入

3 60

输出

4

说明

\(P,Q\)有\(4\)种

1. \(3,60\)
2. \(15,12\)
3. \(12,15\)

4. \(60,3\)

   数据范围

   \(2\leq x_0\leq100000，2\leq y_0\leq1000000\)

   题解

   约定\(D=min(x_0,y_0),M=max(x_0,y_0)\)
   情况1：
   \(M \mod D\neq0\)
   显然，无解。
   情况2：
   \(M \mod D=0\)
   推一波
   \[\because (P,Q)=D,[P,Q]=M\\\therefore P\times Q=(P,Q)[P,Q]=D\times M\\p=P\div D,q=Q\div D,prod=D\div M\\\therefore p\times q=prod\&(p,q)=1\\\]
   当然，暴力枚举\(p\)就可以通过此题，时间复杂度\(O(\sqrt{prod}\times \log(\sqrt{prod}))\)。
   但是这次笔者要将一个更优的解法。
   由推出来的式子可得，我们就要求有多少对\(prod\)的因数互质。
   现将\(prod\)分解质因子得到\(prod\)有\(n\)种质因子。
   对于质因子\(d\)，要么只是\(p\)的质因子，要么只是\(q\)的质因子（如果\(p\)和\(q\)同时拥有这个质因子\(d\)，那么\((p,q)\neq 1\)），并且\(d\)至少要是其中一个的因数（否则\(p\times q\neq prod\)）。
   所以说其中每种质因子都有两种可能，则答案是\(2^n\)。
   时间复杂度\(O(玄学)\)，（最坏\(O(\sqrt{prod})\)，最好\(O(\log(prod))\)）

//C++
#include<bits/locale_facets.h>
#include<stdio.h>
#define forto(name,i,d,u) for(name i=d;i<=u;i++)
inline void output(long long o);
inline long long input();
int main()
{
    short numeral=0;
    int x=input(),y=input();
    if(y%x)return putchar('0'),0;
    y/=x;
    forto(int,i,2,y/i)
    if(!(y%i))
    {
        numeral++;
        while(!(y%i))y/=i;
    }
    if(y>1)numeral++;
    output(1<<numeral);
    return 0;
}
inline void output(long long o)
{
    if(o<0)putchar('-'),o=-o;
    if(o>=10)output(o/10);
    putchar(o%10^'0');
}
inline long long input()
{
    bool minus=false;
    char now=getchar();
    long long i=0;
    for(;!isdigit(now);now=getchar())
    if(now=='-')minus=!minus;
    for(;isdigit(now);now=getchar())i=(i<<3)+(i<<1)+(now^'0');
    return minus?-i:i;
}

//pascal
var
    numeral:1..30;
    x:2..100000;
    i,y:1..1000000;
begin
    readln(x,y);
    if y mod x>0 then
    begin
        write('0');
        halt;
    end;
    y:=y div x;
    i:=2;
    while i<=y div i do
    begin
        if y mod i=0 then
        begin
            inc(numeral);
            while y mod i=0 do y:=y div i;
        end;
        inc(i);
    end;
    if y>1 then inc(numeral);
    write(1 shl numeral);
end.