筛法 - Page 2 - hzwer.com

「BZOJ2818」Gcd
Description给定整数N，求1<=x,y<=N且Gcd(x,y)为素数的数对(x,y)有多少对.Input一个整数NOutput如题SampleInput4SampleOutput4HINThint对于样例(2,2),(2,4),(3,3),(4,2)1<=N<=10^7题解wulala：很水的一道数论题求1<=x,y<=N且Gcd(x,y)为素数的数对(x,y)有多少对枚举每个素数，然后每个素数p对于答案的贡献就是（1~n/p）中有序互质对的个数而求1~m中有序互质对x，y的个数，可以令y>=x, 当y=...
02014年6月15日8,172筛法,欧拉函数

「POJ2478」Farey Sequence
DescriptionTheFareySequenceFnforanyintegernwithn>=2isthesetofirreduciblerationalnumbersa/bwith0<a<b<=nandgcd(a,b)=1arrangedinincreasingorder.ThefirstfewareF2={1/2}F3={1/3,1/2,2/3}F4={1/4,1/3,1/2,2/3,3/4}F5={1/5,1/4,1/3,2/5,1/2,3/5,2/3,3/4,4/5}YoutaskistocalculatethenumberoftermsintheFareysequenceFn.InputThereareseveraltestcases.Eachtestcasehasonlyoneline,whichcontainsap...
02014年6月1日3,237筛法,欧拉函数
「BZOJ1607」[Usaco2008 Dec] Patting Heads 轻拍牛头
Description 今天是贝茜的生日，为了庆祝自己的生日，贝茜邀你来玩一个游戏．贝茜让N(1≤N≤100000)头奶牛坐成一个圈．除了1号与N号奶牛外，i号奶牛与i-l号和i+l号奶牛相邻．N号奶牛与1号奶牛相邻．农夫约翰用很多纸条装满了一个桶，每一张包含了一个独一无二的1到1,000,000的数字．接着每一头奶牛i从柄中取出一张纸条Ai．每头奶牛轮流走上一圈，同时拍打所有编号能整除在纸条上的数字的牛的头，然后做回...
02014年5月22日5,127筛法
「432C」Prime Swaps
Youhaveanarray a[1], a[2], ..., a[n],containingdistinctintegersfrom 1 to n.Yourtaskistosortthisarrayinincreasingorderwiththefollowingoperation(youmayneedtoapplyitmultipletimes):choosetwoindexes, i and j (1 ≤ i < j ≤ n; (j - i + 1) isaprimenumber);swaptheelementsonpositions i and j;inotherwords,youareallowedtoapplythefollowingsequenceofassignments: tmp = a[i], a...
02014年5月21日2,676贪心,筛法
「CF415D」Mashmokh and ACM
Mashmokh'sboss,Bimokh,didn'tlikeMashmokh.Sohefiredhim.MashmokhdecidedtogotouniversityandparticipateinACMinsteadoffindinganewjob.HewantstobecomeamemberofBamokh'steam.Inordertojoinhewasgivensomeprogrammingtasksandoneweektosolvethem.Mashmokhisnotaveryexperiencedprogrammer.Actuallyheisnotaprogrammeratall.Sohewasn'tabletosolvethem.That'swhyheaskedyoutohelphimwiththesetasks.Oneofthesetas...
02014年4月7日3,213递推与动规,筛法
「CF415C」Mashmokh and Numbers
It'sholiday.Mashmokhandhisboss,Bimokh,areplayingagameinventedbyMashmokh.InthisgameMashmokhwritessequenceof n distinctintegersontheboard.ThenBimokhmakesseveral(possiblyzero)moves.Onthefirstmoveheremovesthefirstandthesecondintegerfromfromtheboard,onthesecondmoveheremovesthefirstandthesecondintegeroftheremainingsequencefromtheboard,andsoon.Bimokhstopswhentheboardcontainslessthantwonumbers...
02014年4月7日3,335构造,筛法
「BZOJ2190」[SDOI2008] 仪仗队
Description　　作为体育委员，C君负责这次运动会仪仗队的训练。仪仗队是由学生组成的N*N的方阵，为了保证队伍在行进中整齐划一，C君会跟在仪仗队的左后方，根据其视线所及的学生人数来判断队伍是否整齐(如下图)。　　　　现在，C君希望你告诉他队伍整齐时能看到的学生人数。Input　　共一个数N。Output　　共一个数，即C君应看到的学生人数。SampleInput　　4SampleOutput　　9HINT「数据规模和约定」　　对...
22014年3月18日4,727筛法,欧拉函数
「POJ2262」Goldbach’s Conjecture
DescriptionIn1742,ChristianGoldbach,aGermanamateurmathematician,sentalettertoLeonhardEulerinwhichhemadethefollowingconjecture:Everyevennumbergreaterthan4canbewrittenasthesumoftwooddprimenumbers.Forexample:8=3+5.Both3and5areoddprimenumbers.20=3+17=7+13.42=5+37=11+31=13+29=19+23.Todayitisstillunprovenwhethertheconjectureisright.(Ohwait,Ihavetheproofofcourse,butitistoolongtowriteitonthem...
22014年2月28日3,686筛法