集训队作业solution市复旦附属中学

1、zap 解题市复旦大学附属中学April 3, 20111试题描述题目大意Byteasar the Cryptographerworks on breaking the code of BSA (ByteotianSecurity Agency). He has already found outt whilst deciphering a message hewill have to answer multiple queries of the form. Fivenegers , and ,nd the number ofegairs (, ) satisfying the followi

2、ng conditions:1 1 (, ) = , where (, ) is the greatest common divisor of and .Byteasar would like to automate his work, so he has asked for your help.任务目标Write a programme which:reads from the standard input a list of queries, which the Byteasar has togive answer to.calculates answers to the queries。

3、writes thee to the standard output.11.3输入数据1试题描述输入数据e rst line of the standard inp denoting the number of queries.e following n lines contahreeontains oneeger (1 50 000),egers each: , , , (1 , 50 000), separated by single spa. Each triplet denotes a single query.输出数据Your programme should write lines

4、 to the standard output. e lineshould contain a singleinput.eger: the answer to the ith query from the standard样例输入24 5 26 4 3样例输出32样例解释e pairs satisfying the rst query are: (2, 2), (2, 4) and (4, 2), e pairs sat-isfying the second query are: (6, 3) and (3, 3).题目来源POI XIV(14th) zaptask.pdf中文大意给定 ( 5

5、0 000) 组询问，每组询问给定三个数字 , , ，问你有多少对, 满足 1 与 1 并且 (, ) = 。22试题分析2试题分析先说点题外话，2008 年的国家集训队作业不能在的冬令营的光盘中或者互联网中任何的公开地方可以找到，这里就写一下 14 届 POI 的个人认为不错的有一定难度的试题的解题，以弥补题解的缺失。题目所求就是有多少对 , 满足 1 与 1 并且 (, ) =。当然可以同时将 , 除以 ，将题目转换为满足 1 /and1 / 且 与 互质数的对数。方法一单单查看如何快速求出满足上述式子的数字对数。 点，先求出 1 中有多少数字与 b 互质，然后加起来就是可以一。一般来说解

6、决这个问题是可以通过容斥原理 (Sylvester 公式) 计算得出。Sylvester公式 3 是说:设 , , , , 为有限集合 X 的子集，在 X 中不属于任何集合的元素的权和为：|(1)= () + (1) 把 X 所有的质因子因子的组合（每个质因子可以选或者不选）看作集合 ，代表有多少个数字包含这些因子，那么要求的就是（不含有任何 X 因子的数字）。配合筛法，很容易通过容斥原理，在 2() 的时间内求出了有 1 到 a中有多少数字与 b 互质，其中() 代表了 b 的质因子的个数。现在是怎么求 1 到 a 与 1 到 b 中有多少数字互质呢？其实很简单，对每个 b 都用上面的容斥原

7、理做一遍就可以了，复杂度为：2()。=这个复杂度是不是太大了？没有问题，根据 OEIS1的资料：有以下公式成1URL:(OEIS) A064608,e On-Line Encyclopedia ofeger Sequen32.1方法一2试题分析立： 2() =6 ln + () = ( log ).(2)这个公式较为复杂，我没用弄明白它的道理，可能要用到高级的数学知识。不过想，自然数平均下来每个数的因子数确实也不多吧，所以这么做是线性的。不过这样还是太慢，复杂度高达 ( log )，接下来的优化方法就是让一次( log ) 尽可能回答多个询问。不难想到，当询问的 , 是单调变化的时候，可以通过

8、离线加减上面充斥原理所求的一次回答多个问题，而时间复杂度没有变化。现在变成了如何改变原来的询问的顺序，把他们分成若干段，每段的, 都是单调变化的呢？贪心做，按照 的大小拍个序，每次挑选 的最长不降子序列或者最长不升子序列的长度大的一个做。定理 2.1. 序列 , , , 的最长不降子序列与不升子序列的最大值不会小于 + 1证明.论。 为 的最长不降子序列的长度。接下来分两种情况讨1. 存在一个 ，那么已经满足了命题，不需要继续证明。2. 所有的 ，那么因为 1 + 1，根据抽屉原理所以发现必然存在一个值 ，使得至少存在 + 1 个 的值是相等的。那么这些 对应的 必然是递减的（否则可以从之前的

9、某个 转移过来并且 +1，就不是 了）。因为这 + 1 个 是递减的，那么最长不降子序列的长度至少是 + 1 ，满足了命题。以上结论告诉一次分组就能使 降低为 。定理 2.2. 按照上述规则分组最多只会最多只会找 2 次。42.2方法二2试题分析数字按完全平方数分类，看到从 + 1 到 ( + 1) 最多只证明.会跳 2 次。因为：( + 1) = 2而 1 到 中最多会有 个完全平方数，于是最多会跳 2 次。(3)这个问题有很多种方法，POI 的题解 1 用了一种比较简单的做法，2 中还提到了一种效率更高的方这里介绍一下。而在去年的出题式，有最后，的同学可以参考。询问分割成 段，每段中的 ,

10、 都是单调变化，最后使用容斥原理在 ( log ) 的时间复杂度内完成，能顺利在http:/.pl上通过所有的测试数据。方法二能看完方法一并且彻彻底底搞清楚可能需要花上一段时间，代码高达 250 多行，并不太可能在考场中完成这种方法。不过方法一中的用法更加通用，是值得大家学习的一种算法。不过本题是有更加简单并且高效的算法的，下面介绍一下：这回直接计算 1 1 中有多少对互质的, ，方法还是容斥原理。还是利用 Sylvester 公式，先算出范围内有多少数字的至少是 1，然后减去所有表示比较清晰。for i:=1 to a do至少是 2 个质数数的乘积这里用代码ans:=ans+(a/i)*(

11、b/i)*fi; 代表容斥原理的系数，在这个问题中 满足一下规律：如果 存在一个质因子在 中出现超过一次，那么 = 0。如果 的质因子个数为奇数， = 1。如果 的质因子个数为偶数， = +1。当然可以直接根据定义计算 ，不过下面的程序计算 可能更加高效简洁。54代码f1:=1;for i:=2 to n dofor j:=2 to n div i dofi*j:=fi*j-fi;不理解的同学可以思考一下看看 被哪些值减了。这么做时间复杂度为( log ) ，与筛法的复杂度是一样的。注意到在程序2.2中，对于不同的数字对(, )， 与 的取值各只有可以按照他们可以的取值对这个计算过程进行分组，

12、每规模种可能，组的都是一样的，每次回答问题只需要 () 的时间，最后可以在( 的时间复杂度里解决本题。3总结对于本题这份题解介绍了两种不同的算法。算法能强大，适应性广，可以用不少离线问题的求解，值得大家学习。算法二则解决了算法一的缺点，编程简单容易实现，其中使用的容斥原理的方法也可以用于对 NOI2010 第一题的求解，而的按结果分类的方法也是一种值得大家学习的方法。参考文献1 Xiv olimpiada informatyczna 2006/2007. 小 z 的袜子解题. 国家集训队命题. 算法艺术与信息学竞赛.2, 2010.3, 2004.4代码12345constmaxN = 500

13、00+10;typeTData = record64代码6789101112131415161718192021222324252627282930313233343536373839404142a,b,ind: longend;TGene = record;p,g: end; TArr =FCmp =long;array 1.maxN of long;function (a,b: long):;varn,m,rest: long;v,prt,prev: TArr;gen: array 1.maxN of TGene;ask: array 1.maxN of TData; isPrime: a

14、rray 2.maxN of;procedure swap(var a,b:varlong);t: longbegint:=a;a:=b;b:=t;end;function cmp(a,b: longbeginif aska.aaskb.a):;thenexit(aska.aaskb.a) elseexit(aska.baskb.b);end;function cmp1(a,b: longbegin):;exit(aska.baskb.b);end;procedure sort(l,r: longvari,j,x: long;beginif l=r then exit;i:=l;j:=r; x

15、:=vl+random(r-l+1); while i=j dobeginwhile cmp(vi,x) do inc(i);while cmp(x,vj) do dec(j);if i=j then beginswap(vi,vj);inc(i);dec(j); end;end; sort(l,j);sort(i,r);end;);procedure preFind(x,y: longvar);i: longbegin;if64(x)*y=m thenpreFind(x*y,y); i:=x;while i=m do84代码8081828384858687888990919293949596

16、979899100101102103104105106107108109110111112113114115116beginif geni.g=0 then begingeni.g:=y;geni.p:=i div x;end; inc(i,x);end;end;procedure init;vari,j: longbegin;fillchar(isPrime,sizeof(isPrime),1); for i:=2 to m doif isPrimei thenif64(i)*i=m then beginj:=i*i; while j1 do beginmid:=(l+r) div 2;if

17、 cmp(vi,qmid) r:=midelsel:=mid;end;if rlen then inc(len);qr:=vi;if r1 thenprevvi:=qr-1;end; j:=qlen;for i:=len downto 1 do beginseqi:=j;j:=prevj;end; end;thenfunction calc(a,b: longbeginif (a=0) or (b=0) then exit(0);if b=1 thenexit(a);): long;exit(calc(a,genb.p)-calc(a divend;genb.g,genb.p);procedu

18、re work(var seq: TArr;len: long);104代码154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190vari,ca,cb,ans: longbeginans:=0;ca:=0;cb:=askseq1.b;for i:=1 to len do wiskseqi do beginwhile not(ca=a) and (cb=b)if caa then begindec(ans,calc(cb,ca); dec(ca);endelse if cbb then begininc(cb); inc(ans,calc(ca,cb);endelse begin dec(ans,calc(ca,cb); dec(cb);end; prtind:=ans;end;end;doprocedure