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

来源:2001年NOIP普及组

链接

博客链接

题目链接

题目内容

题目描述

输入二个正整数\(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.
02-12 09:16