题解 P1029 【最大公约数和最小公倍数问题】

· · 题解

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

来源：2001年NOIP普及组

链接

博客链接

题目链接

题解

约定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.