筛法 - hzwer.com

「CF546X」Codeforces Round #304 (Div. 2)
A.SoldierandBananas模拟[crayon-6917107e4d33a235275095/]B.SoldierandBadges排序[crayon-6917107e4d344322192176/]C.SoldierandCards暴力模拟个一百万次。。。[crayon-6917107e4d349962053764/]D.SoldierandNumberGame用筛法得出每个数质因子个数前缀和即可[crayon-6917107e4d34d021069841/]E.SoldierandTraveling我比较愚蠢写了网络流。。正解是什么我不知道[crayon-6917107e4d355339211830/] ...
52015年5月23日4,929模拟,筛法,网络流

「JoyOI」五月有奖赛暨Loi 55 Round #1 Day1
题解http://pan.baidu.com/s/1bnjO0ij选择题（byDarkfalmes）[crayon-6917107e4e9cb161618261/]王的对决！(byrainheart&seavot)[crayon-6917107e4e9d6472765130/]dC的肥皂（byskyfall（Orz））60暴力[crayon-6917107e4e9dc464798042/]DQS和序列（by帝江&Darkfalmes）[crayon-6917107e4e9e3610729127/] ...
22015年4月30日4,374递推与动规,线段树,筛法,广度搜索,莫比乌斯反演
「POJ2154」Color
DescriptionBeadsofNcolorsareconnectedtogetherintoacircularnecklaceofNbeads(N<=1000000000).Yourjobistocalculatehowmanydifferentkindsofthenecklacecanbeproduced.YoushouldknowthatthenecklacemightnotuseupalltheNcolors,andtherepetitionsthatareproducedbyrotationaroundthecenterofthecircularnecklaceareallneglected.YouonlyneedtooutputtheanswermoduleagivennumberP.InputThefirstlineoftheinputisa...
02015年4月24日4,810置换,筛法,快速幂,欧拉函数
「BZOJ3813」奇数国
Description在一片美丽的大陆上有100000个国家，记为1到100000。这里经济发达，有数不尽的账房，并且每个国家有一个银行。某大公司的领袖在这100000个银行开户时都存了3大洋，他惜财如命，因此会不时地派小弟GFS清点一些银行的存款或者让GFS改变某个银行的存款。该村子在财产上的求和运算等同于我们的乘法运算，也就是说领袖开户时的存款总和为3100000。这里发行的软妹面额是最小的60个素数（p1=2,p2=3,…,p60=281），任何人...
02015年1月22日6,213线段树,筛法,欧拉函数,乘法逆元
「POJ3696」The Luckiest number
DescriptionChinesepeoplethinkof'8'astheluckydigit.Bobalsolikesdigit'8'.Moreover,BobhashisownluckynumberL.NowhewantstoconstructhisluckiestnumberwhichistheminimumamongallpositiveintegersthatareamultipleofLandconsistofonlydigit'8'.InputTheinputconsistsofmultipletestcases.EachtestcasecontainsexactlyonelinecontainingL(1≤L≤2,000,000,000).Thelasttestcaseisfollowedbyalinecontainingazero.O...
02015年1月16日4,979筛法,快速幂,欧拉函数
「POJ1284」Primitive Roots
DescriptionWesaythatintegerx,0<x<p,isaprimitiverootmodulooddprimepifandonlyiftheset{(ximodp)|1<=i<=p-1}isequalto{1,...,p-1}.Forexample,theconsecutivepowersof3modulo7are3,2,6,4,5,1,andthus3isaprimitiverootmodulo7.Writeaprogramwhichgivenanyoddprime3<=p<65536outputsthenumberofprimitiverootsmodulop.InputEachlineoftheinputcontainsanoddprimenumbersp.Inputisterminatedbytheend-of-...
02014年12月29日4,950筛法,欧拉函数
「BZOJ2186」[SDOI2008] 沙拉公主的困惑
Description　　大富翁国因为通货膨胀，以及假钞泛滥，政府决定推出一项新的政策：现有钞票编号范围为1到N的阶乘，但是，政府只发行编号与M!互质的钞票。房地产第一大户沙拉公主决定预测一下大富翁国现在所有真钞票的数量。现在，请你帮助沙拉公主解决这个问题，由于可能张数非常大，你只需计算出对R取模后的答案即可。R是一个质数。Input第一行为两个整数T，R。R<=10^9+10，T<=10000，表示该组中测试数据数目，R...
62014年12月28日9,238筛法,欧拉函数,乘法逆元
「BZOJ2721」[Violet 5] 樱花
DescriptionInputOutputHINT题解设n!=z，y=z+d1/x+1/y=1/z1/x+1/(z+d)=1/z(x+z+d)/(x*z+dx)=1/zz(x+z+d)=x*z+dxz^2+dz=dxx=z^2/d+z发现就是求z^2的约数个数分解质因数随便做。。[crayon-6917107e50931200280656/] ...
12014年12月21日5,364筛法
「codechefSUBLCM」Subarray LCM
题解首先筛法求100w以内的素数，同时记录每个质数最小的质因数然后用last[x]记录质因数x的最后出现位置，用tmp表示max{i}（满足i到当前位置now间的所有数互质）每次读入一个数a[now]，对a[now]分解质因数，更新tmp，更新last[x]tmp=max(tmp,last[t]);last[t]=i;最后用i-tmp更新答案我表达能力极弱啊。。。[crayon-6917107e50c8b192868949/] ...
02014年9月24日3,325筛法
「BZOJ1025」[SCOI2009] 游戏
Descriptionwindy学会了一种游戏。对于1到N这N个数字，都有唯一且不同的1到N的数字与之对应。最开始windy把数字按顺序1，2，3，……，N写一排在纸上。然后再在这一排下面写上它们对应的数字。然后又在新的一排下面写上它们对应的数字。如此反复，直到序列再次变为1，2，3，……，N。如：123456对应的关系为1->22->33->14->55->46->6windy的操作如下123456231546312456123546231456312546123456这时，我们就...
02014年9月13日7,558递推与动规,筛法
「BZOJ3629」[JLOI2014] 聪明的燕姿
Description阴天傍晚车窗外未来有一个人在等待向左向右向前看爱要拐几个弯才来我遇见谁会有怎样的对白我等的人他在多远的未来我听见风来自地铁和人海我排着队拿着爱的号码牌城市中人们总是拿着号码牌，不停寻找，不断匹配，可是谁也不知道自己等的那个人是谁。可是燕姿不一样，燕姿知道自己等的人是谁，因为燕姿数学学得好！燕姿发现了一个神奇的算法：假设自己的号码牌上写着数字S，那么自己等的人手上的号码牌数字的所有正约数...
12014年8月14日6,757深度搜索,筛法
「NOIP模拟赛」hash函数
「问题描述」明明觉得hash是个好算法，代码短、效率高。某天，他碰到了一个求正方形个数的问题，于是很淡定地枚举对角线，然后用hash判存在，妥妥的搞定，但是提交后却wa了几个点。仔细观察其hash函数为：h=x*y+x+y。为了让明明知道这个函数存在什么问题，对于给出一个h值，请你来告诉他有多少对(x，y)满足上述式子(max(x,y)≤h；h，x，y都为非负整数)?「输入格式」多组测试数据，第一行为测试点的个数T，接下来每一行一个整数h，...
02014年7月10日3,242筛法