欧拉函数 - hzwer.com

2017 训练赛 1 by hzwer
「poj1054」TheTroublesomeFrog（恼人的青蛙）「poj1037」decorativefence「hdu2197」本原串「poj2112」OptimalMilkin「bzoj4010」[HNOI2015]菜肴制作「hdu2462」TheLuckiestnumber「bzoj3172」[Tjoi2013]单词「poj1054」TheTroublesomeFrog（恼人的青蛙）首先O(n^3)的算法是显然的，即枚举两个点，check一下这条路径上所有点，由于这道题时限放的比较宽，实际上图可以直接用二维的bool数组存下来网络上的题解大多...
02017年3月7日9,885递推与动规,贪心,最大流,二分法,AC自动机,快速幂,拓扑排序,欧拉函数

「BZOJ4173」数学
Description Input 输入文件的第一行输入两个正整数。Output 如题SampleInput56SampleOutput240HINT N,M<=10^15题解贴个大爷的式子：http://blog.csdn.net/popoqqq/article/details/46820313[crayon-673fbdb666dcf694812066/] ...
32015年7月14日5,069欧拉函数
「POJ2154」Color
DescriptionBeadsofNcolorsareconnectedtogetherintoacircularnecklaceofNbeads(N<=1000000000).Yourjobistocalculatehowmanydifferentkindsofthenecklacecanbeproduced.YoushouldknowthatthenecklacemightnotuseupalltheNcolors,andtherepetitionsthatareproducedbyrotationaroundthecenterofthecircularnecklaceareallneglected.YouonlyneedtooutputtheanswermoduleagivennumberP.InputThefirstlineoftheinputisa...
02015年4月24日4,324置换,筛法,快速幂,欧拉函数
「BZOJ3884」上帝与集合的正确用法
Description根据一些书上的记载，上帝的一次失败的创世经历是这样的：第一天，上帝创造了一个世界的基本元素，称做“元”。第二天，上帝创造了一个新的元素，称作“α”。“α”被定义为“元”构成的集合。容易发现，一共有两种不同的“α”。第三天，上帝又创造了一个新的元素，称作“β”。“β”被定义为“α”构成的集合。容易发现，一共有四种不同的“β”。第四天，上帝创造了新的元素“γ”，“γ”被定义为“β”的集合。...
02015年2月28日8,996欧拉函数
「BZOJ3813」奇数国
Description在一片美丽的大陆上有100000个国家，记为1到100000。这里经济发达，有数不尽的账房，并且每个国家有一个银行。某大公司的领袖在这100000个银行开户时都存了3大洋，他惜财如命，因此会不时地派小弟GFS清点一些银行的存款或者让GFS改变某个银行的存款。该村子在财产上的求和运算等同于我们的乘法运算，也就是说领袖开户时的存款总和为3100000。这里发行的软妹面额是最小的60个素数（p1=2,p2=3,…,p60=281），任何人...
02015年1月22日5,813线段树,筛法,欧拉函数,乘法逆元
「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,654筛法,快速幂,欧拉函数
「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,188筛法,欧拉函数
「BZOJ2186」[SDOI2008] 沙拉公主的困惑
Description　　大富翁国因为通货膨胀，以及假钞泛滥，政府决定推出一项新的政策：现有钞票编号范围为1到N的阶乘，但是，政府只发行编号与M!互质的钞票。房地产第一大户沙拉公主决定预测一下大富翁国现在所有真钞票的数量。现在，请你帮助沙拉公主解决这个问题，由于可能张数非常大，你只需计算出对R取模后的答案即可。R是一个质数。Input第一行为两个整数T，R。R<=10^9+10，T<=10000，表示该组中测试数据数目，R...
62014年12月28日8,862筛法,欧拉函数,乘法逆元
「BZOJ2705」[SDOI2012] Longge的问题
DescriptionLongge的数学成绩非常好，并且他非常乐于挑战高难度的数学问题。现在问题来了：给定一个整数N，你需要求出∑gcd(i,N)(1<=i<=N)。Input一个整数，为N。Output一个整数，为所求的答案。SampleInput6SampleOutput15HINT「数据范围」对于60%的数据，0<N<=2^16。对于100%的数据，0<N<=2^32。题解题目中要求出∑gcd(i,N)(1<=i<=N)。枚举n的约数k，令s(k)为满足gcd(m,n)=k,(1<...
02014年6月15日6,435欧拉函数
「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,555筛法,欧拉函数
「POJ2407」Relatives
DescriptionGivenn,apositiveinteger,howmanypositiveintegerslessthannarerelativelyprimeton?Twointegersaandbarerelativelyprimeiftherearenointegersx>1,y>0,z>0suchthata=xyandb=xz.InputThereareseveraltestcases.Foreachtestcase,standardinputcontainsalinewithn<=1,000,000,000.Alinecontaining0followsthelastcase.OutputForeachtestcasethereshouldbesinglelineofoutputansweringthequestionposed...
02014年6月1日3,277欧拉函数
NOI2002Robot
DescriptionInputOutputSampleInput3213251SampleOutput8675HINT90号机器人有10个老师，加上它自己共11个。其中政客只有15号；军人有3号和5号；学者有8个，它们的编号分别是：2,6,9,10,18,30,45,90。题解为何我觉得这题十分恶心f[i][0]表示前i个因数（不含2）的乘积m和它的老师中政客的独立数之和（包括自己）f[i][1]表示前i个因数（不含2）的乘积m和它的老师中军人的独立数之和（包括自己）[crayon-673fbdb677fa602742...
12014年6月1日3,430快速幂,欧拉函数