《Hankson的趣味题》解题报告

本文格式为Word版，下载可任意编辑——《Hankson的趣味题》解题报告NOIP2023提高组解题报告

Bysx349

核心算法思想：数论主要数据结构：其他辅助知识：时间繁杂度：O(NM)空间繁杂度：O(M)

给定a0,a1,b0,b1，求满足如下条件的数x的个数：

gcd(x,a0)?a1

lcm(x,b0)?b1

由题意，我们得到

gcd(x,a0)?a1??(1)

lcm(x,b0)?b1??(2)由（1）式得

gcd(xa0,)?1??(3)a1a1由（2）式得

gcd(x,b0)?gcd(x?x?b0b1b1b1,b0?)?1x?b0x?b0b1b1gcd(,)?1??(4)b0x由（3）和（4）我们可知a1x且xb1，所以若b1moda1?0那么必然无解。我们用a'来代替

a0b1b1x，用b'来代替，用k来代替，用t来代替，所以a1a1a1b0gcd(a',t)?1??(5)kgcd(b',)?1??(6)t我们将t进行质因数分解，假设

t?a1p1a2p2a3p3??anpn

（1）在这里，我们可以得到一个简朴的算法。

考虑通过t的因子表，计算出t的所有约数。然后，逐个计算最大公约数和最小公倍数。最终的时间繁杂度与t的质因数指数有关，每一次的最大公约数或最小公倍数计算时间繁杂度为O(logM)，所以最终每一组数据的时间繁杂度为O(logM)。但由于M最大可以达到2000000000，所以极限数据的总时间繁杂度上限会达到几千万左右（当然，由于并不完全是最差数据，所以实际上的时间繁杂度远小于这个数字）。（在实际比赛中，宋文杰神牛据称用Miller-Rabin实时求素数加上简朴算法最终也全部通过，但由于没有获得当时的实际程序，暂时无法分析）因此，我们需要一个更加简单的方法。（2）重新考虑t的质因数分解。

①显然，假使在a1a2a3??an中有至少一个是a'的质因数，那么必然不能满足（5）式，所以，我们可以把a1a2a3??an中是a'的质因数的数排除掉。

②另一方面，假使在a1a2a3??an中有至少一个是b'的质因数，假设其中某一个为ai，那么显然

kp的质因数中必然不能有ai（否则不能满足（6）式），因此t中必然有aii这一部分，t所以，我们可以不用考虑所有的ai。

（可以看出，假使在有某个ai既是a'的质因数，又是b'的质因数，则我们既不能选择ai，又必需将ai全部选择，必然无解）

③在剩下的一系列ai中，无论怎样选择都必然能够满足条件，假设最终仍要考虑的ai有

ai1ai2ai3??aik，那么我们拥有的选择个数就是?(1?pij)。

j?1k

在拿到题目之后我的第一反应就是数论，然后就是进行一系列的推导。尽管如此，我在上述（1）的地方也曾经想选择简朴的算法，但是面对令人汗颜的一长串数字，感觉在这么大的数字之下简朴算法必然是超时的（尽管在后来的分析中发现可能并不一定超时），因此就放弃了，但在完成了后面几题之后回过来看看，进行进一步的推导以后，得到了（2）这种做法。

根据我赛后对几个神牛的询问，大多在这里考虑了类似宋文杰神牛的做法，并没有用到后面的分析，其中全部AC的并不多。我又想起去年省选的第三题同样是一道比较繁杂的数学题，我和宋文杰进行探讨以后得到了一个二维的递推，宋神牛的看法是完全可以进一步优化到一维，但是会更加繁杂。由此我得到的启示是，在赛场上，要合理的安排好理论分析与编程的时间比例，考虑用较简便但同样可以解决问题的方法来使考试时间利用最大化。

2.Hankson的趣味题

(son.pas/c/cpp)

Hanks博士是BT（Bio-Tech，生物技术）领域的知名专家，他的儿子名叫Hankson。现在，刚刚放学回家的Hankson正在思考一个好玩儿的问题。

今天在课堂上，老师讲解了如何求两个正整数c1和c2的最大公约数和最小公倍数。现在Hankson认为自己已经熟练的把握了这些知识，他开始思考一个“求公约数〞和“求公倍数〞之类问题的“逆问题〞，这个问题是这样的：已知正整数a0,a1,b0,b1，设某未知正整数x满足：

1．x和a0的最大公约数是a1；2．x和b0的最小公倍数是b0;

Hankson的“逆问题〞就是求出满足条件的正整数x。但稍加思考之后，他发现这样的x并不唯一，甚至可能不存在。因此他转而开始考虑如何求解满足条件的x的个数。请你帮助他编程求解这个问题。

输入文件名为son.in。第一行为一个正整数n，表示有n组输入数据。接下来的n行每行一组输入数据，为四个正整数a0,a1,b0,b1，每两个整数之间用一个空格隔开。输入数据保证a0能被a1整除，b1能被b0整除。

输出文件son.out共n行。每组输入数据的输出结果占一行，为一个整数。对于每组数据：若不存在这样的x，请输出0；若存在这样的x，请输出满足条件的x的个数；

son.in241196288951371776son.out62

第一组输入数据，x可以是9、18、36、72、144、288，共有6个。其次组输入数据，x可以是48、1776，共有2个。

对于50%的数据，保证有1≤a0，a1，b0，b1≤10000，且n≤100。

对于100%的数据，保证有1≤a0，a1，b0，b1≤2,000,000,000，且n≤2000。

（简朴求素数，根据需要更新素数表P）{

PROG:NOIP2023_sonLANG:PASCALID:xyj-flash

}

ProgramSon;Var

P,PT,Num:Array[0..100000]ofLongint;

//P：素数表；//PT：质因数；//Num：质因数指数

Sum,A0,A1,B0,B1,T,I,N,J,R,Top:Longint;//Top：当前素数表的上界

Flag:Boolean;

ProcedureMorePrime(T:Longint);//更新素数表VarI,J:Longint;BeginI:=Top+1;IfNotOdd(I)ThenInc(I);WhileI0)and(J0ThenBeginInc(P[0]);P[P[0]]:=I;End;I:=I+2;End;Top:=T;End;

ProcedureGetFactor(T:Longint);//分解质因数VarI,T1:Longint;BeginI:=1;T1:=T;While(T11)and(I1ThenBeginInc(PT[0]);PT[PT[0]]:=T1;Num[PT[0]]:=1;End;End;

ProcedureWork1(T:Longint);//排除a'的质因数VarI:Longint;BeginForI:=1toPT[0]do

IfTModPT[I]=0ThenNum[I]:=0;End;

Begin

Assign(Input,'son.in');Assign(Output,'son.out');Reset(Input);Rewrite(Output);Read(N);

P[1]:=2;P[2]:=3;P[3]:=5;P[0]:=3;Top:=5;ForI:=1toNdoBeginFillchar(PT,Sizeof(PT),0);Fillchar(Num,Sizeof(Num),0);Read(A0,A1,B0,B1);A0:=A0DivA1;IfRound(Sqrt(A0))>TopThenMorePrime(Round(Sqrt(A0)));B0:=B1DivB0;IfRound(Sqrt(B0))>TopThenMorePrime(Round(Sqrt(B0)));IfB1ModA10ThenBeginWriteln(0);Continue;End;T:=B1DivA1;IfRound(Sqrt(T))>TopThenMorePrime(Round(Sqrt(T)));GetFactor(T);Work1(A0);Flag:=False;//排除b'的质因数ForJ:=1toPT[0]doBegin

IfB0ModPT[J]=0Then

IfNum[J]=0ThenFlag:=TrueElseNum[J]:=0;

IfFlagThenBreak;End;IfFlagThenBegin

Writeln(0);Continue;End;Sum:=1;ForJ:=1toPT[0]do

Sum:=Sum*(Num[J]+1);Writeln(Sum);End;

Close(Input);Close(Output);End.

IfFlagThenBreak;End;If