数学 - Page 13 - 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,188筛法,欧拉函数

「泉七培训 – 郑予凡」致命漏洞
对于55%的数据，此题可以用个简单的矩阵乘法100%只要加上高精度即可，但是考场上高精度打萎了只有55%...没发现挂哪了。。。[crayon-66364604b1e63846330097/] ...
02014年6月14日3,308高精度,矩阵乘法
「BZOJ2510」弱题
Description有M个球，一开始每个球均有一个初始标号，标号范围为1～N且为整数，标号为i的球有ai个，并保证Σai = M。每次操作等概率取出一个球（即取出每个球的概率均为1/M），若这个球标号为k（k < N），则将它重新标号为k +1；若这个球标号为N，则将其重标号为1。（取出球后并不将其丢弃）现在你需要求出，经过K次这样的操作后，每个标号的球的期望个数。Input第1行包含三个正整数N，M，K，表示了标号与球的...
62014年6月6日4,621矩阵乘法
「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,149欧拉函数
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-66364604b2f5c21720...
12014年6月1日3,306快速幂,欧拉函数
「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,253筛法,欧拉函数
「POJ2891」Strange Way to Express Integers
DescriptionElinaisreadingabookwrittenbyRujiaLiu,whichintroducesastrangewaytoexpressnon-negativeintegers.Thewayisdescribedasfollowing:Choose k differentpositiveintegers a1, a2, …, ak.Forsomenon-negative m,divideitbyevery ai (1≤ i ≤ k)tofindtheremainder ri.If a1, a2,…, ak areproperlychosen,mcanbedetermined,thenthepairs(ai, ri)canbeusedtoexpress m.“Itiseasytocalculate...
02014年5月31日3,632模线性方程组
「POJ1006」生理周期
Description人生来就有三个生理周期，分别为体力、感情和智力周期，它们的周期长度为23天、28天和33天。每一个周期中有一天是高峰。在高峰这天，人会在相应的方面表现出色。例如，智力周期的高峰，人会思维敏捷，精力容易高度集中。因为三个周期的周长不同，所以通常三个周期的高峰不会落在同一天。对于每个人，我们想知道何时三个高峰落在同一天。对于每个周期，我们会给出从当前年份的第一天开始，到出现高峰的天数（不一定是第...
32014年5月31日1,071模线性方程组
NOI2002荒岛野人Savage
DescriptionInput第1行为一个整数N(1<=N<=15)，即野人的数目。第2行到第N+1每行为三个整数Ci,Pi,Li(1<=Ci,Pi<=100,0<=Li<=106)，表示每个野人所住的初始洞穴编号，每年走过的洞穴数及寿命值。Output仅包含一个数M，即最少可能的山洞数。输入数据保证有解，且M不大于106。SampleInput3134273321SampleOutput6该样例对应于题目描述中的例子。题解枚举m>=max{c[i]}使得对于每一对i，j有c[i]+x...
22014年5月31日4,414扩展欧几里得算法
「BZOJ1005」[HNOI2008] 明明的烦恼
Description自从明明学了树的结构,就对奇怪的树产生了兴趣......给出标号为1到N的点,以及某些点最终的度数,允许在任意两点间连线,可产生多少棵度数满足要求的树?Input第一行为N(0<N<=1000),接下来N行,第i+1行给出第i个节点的度数Di,如果对度数不要求,则输入-1Output一个整数,表示不同的满足要求的树的个数,无解输出0SampleInput31-1-1SampleOutput2HINT 两棵树分别为1-2-3;1-3-2 题解该题运用到了...
62014年5月30日10,713高精度,prufer编码,排列组合
「BZOJ1211」[HNOI2004] 树的计数
Description一个有n个结点的树，设它的结点分别为v1,v2,…,vn，已知第i个结点vi的度数为di，问满足这样的条件的不同的树有多少棵。给定n，d1,d2,…,dn，编程需要输出满足d(vi)=di的树的个数。Input第一行是一个正整数n，表示树有n个结点。第二行有n个数，第i个数表示di，即树的第i个结点的度数。其中1<=n<=150，输入数据保证满足条件的树不超过10^17个。Output输出满足条件的树有多少棵。SampleInput42121SampleOutpu...
02014年5月30日5,057prufer编码,排列组合
「BZOJ1004」[HNOI2008] Cards
Description小春现在很清闲,面对书桌上的N张牌,他决定给每张染色,目前小春只有3种颜色:红色,蓝色,绿色.他询问Sun有多少种染色方案,Sun很快就给出了答案.进一步,小春要求染出Sr张红色,Sb张蓝色,Sg张绝色.他又询问有多少种方案,Sun想了一下,又给出了正确答案.最后小春发明了M种不同的洗牌法,这里他又问Sun有多少种不同的染色方案.两种染色方法相同当且仅当其中一种可以通过任意的洗牌法(即可以使用多种洗牌法,而每种方法可...
22014年5月26日9,104背包动规,置换,乘法逆元