第二次作业解题报告ctsc奥运抽奖

JiaZhihaoFromNo.2MiddleInShijizhuang,OfHebei给定一个{2,3,4,5,6的子集YLYL，一个数cA当且仅当存在abL满足a*bc。定义l(kLkf10

f()02SdSSd后的集合，q是一个给定的非负整数。定义集合Ta,bd|dLl(a|dd|l(b，现在有多组询问，每一组询问包含两个数abf(Ta,bmodp。20%1ab≤1000，n2000；1a≤b≤100000，n≤100000，p,q≤2×10960%的数据点满足：p子任务一：构造出集合L假设子集为{2,3,5}L1一个元素（1剔除出集合中，P2依次向后移，直到找到第一个数kL使得k*2L中的最大P2停在这个位置。后的情况，所以我们不妨用因式分解法L中的数。我们可以用取对数的方法来比较大小，对于n100000的规模，相信是不会fAf(A)df(A\d)q*d*f(A\df(A)*q1d*qf(A\d)*qq2*d*f(A\d)q*f(A)1[q*f(A\d)1]*(qdq*f(A)1(q*kBACABCABC则q*f(A)1(q*f(B)1)*(q*f(C)f(A)f(B)f(C)q*f(B)*ffA。2，3，5首先，若bmoda0，显然Ta,bf(Ta,b0若bmoda0，则我们设a2X1*3Y1*5Z1，b2X2*3Y2*5Z2

立方体(x1,y1,z1(x2,y2,z2)话三维线的规模大致是500*500*500*1.25*108这显然是程序所56选成底，类似的例子还有集合{6}。注意到这个细节后，可以说，这道难题已经被我们攻克了注意对数学进行必要分析PROGRAMPROGRAMvolunteer; arr=array[1..3]oflongint;arr1=array[1..2]ofarr;next,lch,rch:array[1..num]oflongint;val:array[1..num]ofint64;lp,rp:array[1..num]ofarr;a:array[0..100000]ofarr;prime:Array[1..3]ofint64;b:array[1..3]ofarray[0..100000]ofint64;shu:array[1..5]ofarray[1..3]oflongint;p,z:array[1..5]oflongint;Procedurefori:=1tondonow[i]:=now[i]+shu[k][i];Functionx:=a*bmodsize;x:=q*xmodsize;exit((x+a+b)modsize);Functionfork:=1tondoifprime[k]<>0thent:=t+(a[k]-b[k])*ln(prime[k]);Functionwhileleft<rightdobeginmid:=(left+right+1)divifnotbig(a[mid],b)thenleft:=midelseright:=mid-1;abs(a[left][1]-b[1])+abs(a[left][2]-b[2])+abs(a[left][3]-b[3])=0thenexit(true)elseexit(false);Functionmid:=(lp[v][c]+rp[v][c])div2;if(d[1][c]<=lp[v][c])and(rp[v][c]<=d[2][c])thenbeginifc<nthenfind:=find(next[v],c+1)elsefind:=val[v];elseifd[1][c]<=midthenk1:=find(lch[v],c)elsek1:=0;ifd[2][c]>=mid+1thenk2:=find(rch[v],c)elsek2:=0;Proceduremid:=(lp[v][c]+rp[v][c])div2;iflp[v][c]<rp[v][c]thenifc<nthenbeginelseiflch[v]=0then val[v]:=calc(val[next[lch[point[2]]]+v-]]+v- val[v]:=calc(val[next[lch[point[1]]]+v-]]+v-elsebeginfori:=1tondoval[v]:=(val[v]*b[i][lp[v][i]])modiflp[v][1]+lp[v][2]+lp[v][3]=0thenval[v]:=0;ifnotexist(lp[v])thenval[v]:=0;fori:=1to5dobeginifk=1thenbegininc(ji);z[ji]:=i+1;end;end;{fori}if(con=1)thenelseif(con=3)thenbeginelseifconand21>0thenbegininc(n);prime[n]:=2;end;ifconand9>0thenbegininc(n);prime[n]:=3;end;ifconand2>0thenbegininc(n);prime[n]:=5;end;fori:=1tojiforj:=1tondowhilez[i]modprime[j]=0dobeginz[i]:=z[i]divprime[j];end;{forij}fori:=1to100000dobeginforj:=1tojidobeginwhilenotbig(now,a[i-1])dobeginifbig(best,now)thenbest:=now;end;{forj}forj:=1tondoifa[i][j]>max[j]thenend;{forend;{forfori:=1tondobeginforj:=1tomax[i]dob[i][j]:=(b[i][j-1]*prime[i])modsize;end;{fori}fortest:=1tonumtestdobegina[ended][3])thenwri elsebegin end;{fortest}距2008年奥运会开幕还有90天时，CTSC准备为们举行一次抽奖活动。作为的一员，你对这次抽奖活动自然是万分期待。CTSC介绍了抽奖活动的规则。设总共有p个参加抽奖的，开始时每一个领取一个0到p-1的号码。任意两个领取的号码不同。屏幕的正是五能是睁开的，有的是闭上的。如果所有的眼睛都闭上了，工作人员需要重新按一下按5、6（01都不是好数字。定义幸运数字如下：2l1l2(可能相等)用L表示所有数字的集合，例如，如果、晶晶的眼睛是睁开的，、迎迎、妮例子中，l(1)=2，l(4)=6等等。xf102SdSSd后的集合，q在a和b产生以后 的就确定了，他的号码是f(Ta,b)除以p的余数。工人员会产生多次a，b，这样就能形成多个者。但是，抽奖现场的程序需要很长的时间输入的第一行给出用空格隔开的5个数，每个数不是0就是1，分别表示、晶晶、第二行给出了用空格隔开的两个数，p和q。其中p表示参加抽奖的的人数，q、nab输出共n行，每一行一个整数，表示一次抽奖奖者的号码。顺序与输入的n对a、b一一对应。当然，一个人可能多次。1001100013124和迎迎的眼睛是睁开的，因此，前面15个幸运数字是、、、 、 、、、 、、 。l(1)=2，l(10)=40。既是2的倍数，又是40的约数的幸运数字有、、、、、。所以T1,10={2,4,8,10,20,40}。T1,10的特征值的计f() })4002