《Hankson的趣味题》解题报告

NOIP2009提高组解题报告

By sx349

【摘要】

核心算法思想：数论 主要数据结构： 其他辅助知识： 时间复杂度：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?)?1 x?b0x?b0b1b1gcd(,)?1??(4)b0x由（3）和（4）我们可知a1x且xb1，所以若b1 mod a1?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.in 2 41 1 96 288 95 1 37 1776 son.out 6 2

【说明】

第一组输入数据，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: NOIP2009_son LANG: PASCAL ID: xyj-flash

}

Program Son; Var

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

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

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

Flag:Boolean;

Procedure MorePrime(T:Longint); //更新素数表 Var

I,J:Longint; Begin

I:=Top+1;

If Not Odd(I) Then Inc(I); While I<=T do Begin J:=1;

While (P[J]<=Round(Sqrt(I))) and (I Mod P[J]<>0) and (J<=P[0]) do

Inc(J);

If I Mod P[J]<>0 Then Begin Inc(P[0]); P[P[0]]:=I; End; I:=I+2; End; Top:=T; End;

Procedure GetFactor(T:Longint); //分解质因数 Var

I,T1:Longint; Begin

I:=1;T1:=T;

While (T1<>1) and (I<=P[0]) and (P[I]<=Round(Sqrt(T))) do Begin If T1 Mod P[I]=0 Then Begin Inc(PT[0]);

PT[PT[0]]:=P[I];

While T1 Mod P[I]=0 do Begin Inc(Num[PT[0]]); T1:=T1 Div P[I]; End; End;