扩展欧几里得算法 - hzwer.com

2017ACM萧山训练第2场(NWERC 2008)
A:EquilibriumMobile最终天平平衡的状态下，每个结点x满足w[x]*(2^dep[x])相等统计所有的w[x]*(2^dep[x])，答案是叶子数减去出现次数最多的个数[crayon-6939338c4e421055801477/]B:ProvingEquivalences答案是max{入度为0的连通块个数，出度为0的连通块个数}特判连通块为1的情况每个连通块，出度0的点，向其它入度为0的连边，使得形成一个环[crayon-6939338c4e437433505661/]C:Catvs.Dog找出所有相互不兼容的人，将他们连边...
12017年8月8日6,615递推与动规,贪心,单调队列,图的连通,二分图匹配,扩展欧几里得算法

「NOIP模拟赛」jams倒酒
Jams是一家酒吧的老板，他的酒吧提供2种体积的啤酒，aml和bml，分别使用容积为aml和bml的酒杯来装载。酒吧的生意并不好。Jams发现酒鬼们都很穷，不像他那么土豪。有时，他们会因为负担不起aml或者bml酒的消费，而不得不离去。因此，Jams决定出手第三种体积的啤酒(较小体积的啤酒)。Jams只有两种杯子，容积分别为aml和bml，而且啤酒杯是没有刻度的。他只能通过两种杯子和酒桶间的互相倾倒来得到新的体积的酒。倒酒步骤为:规定a&...
02014年10月23日3,846扩展欧几里得算法
「BZOJ1951」[SDOI2010] 古代猪文
Description“在那山的那边海的那边有一群小肥猪。他们活泼又聪明，他们调皮又灵敏。他们自由自在生活在那绿色的大草坪，他们善良勇敢相互都关心……”——选自猪王国民歌很久很久以前，在山的那边海的那边的某片风水宝地曾经存在过一个猪王国。猪王国地理位置偏僻，实施的是适应当时社会的自给自足的庄园经济，很少与外界联系，商贸活动就更少了。因此也很少有其他动物知道这样一个王国。猪王国虽然不大，但是土地肥沃，屋舍俨然...
22014年9月14日9,386快速幂,排列组合,模线性方程组,扩展欧几里得算法
「NOIP模拟赛」合唱队形
「问题描述」学校要进行合唱比赛了，于是班主任小刘准备给大家排个队形。他首先尝试排成m1行，发现最后多出来a1个同学；接着他尝试排成m2行，发现最后多出来a2个同学，……，他尝试了n种排队方案，但每次都不能让同学们正好排成mi行。于是小刘寻求同事小明的帮助，以便给同学们排好队形。但小刘来去太匆忙，忘记告诉小明他们班有多少人了。没办法，现在只能根据上述信息求个满足要求的最小的数字来作为人数了。虽然小明年轻时是理科...
02014年7月10日4,314扩展欧几里得算法
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,761扩展欧几里得算法
「POJ2115」C Looooops
DescriptionACompilerMystery:WearegivenaC-languagestyleforloopoftype [crayon-6939338c5195d207579098/]I.e.,aloopwhichstartsbysettingvariabletovalueAandwhilevariableisnotequaltoB,repeatsstatementfollowedbyincreasingthevariablebyC.WewanttoknowhowmanytimesdoesthestatementgetexecutedforparticularvaluesofA,BandC,assumingthatallarithmeticsiscalculatedinak-bitunsignedintegertype(withvalu...
22014年3月21日4,155扩展欧几里得算法
「BZOJ1477」青蛙的约会
Description两只青蛙在网上相识了，它们聊得很开心，于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上，于是它们约定各自朝西跳，直到碰面为止。可是它们出发之前忘记了一件很重要的事情，既没有问清楚对方的特征，也没有约定见面的具体位置。不过青蛙们都是很乐观的，它们觉得只要一直朝着某个方向跳下去，总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上，不然是永远都不可能碰面的。为了帮助这两只...
12014年3月21日5,569扩展欧几里得算法
「BZOJ1385」[Baltic2000] Division expression
Description除法表达式有如下的形式:X1/X2/X3.../Xk其中Xi是正整数且Xi<=1000000000(1<=i<=k,K<=10000)除法表达式应当按照从左到右的顺序求，例如表达式1/2/1/2的值为1/4.但可以在表达式中国入括号来改变计算顺序，例如(1/2)/(1/2)的值为1.现给出一个除法表达式E，求是告诉是否可以通过增加括号来使其为E',E'为整数Input先给出一个数字D，代表有D组数据.每组数据先给出一个数字N，代表这组数据将有N个...
02014年3月16日3,622扩展欧几里得算法
NOIP2012同余方程
题目描述求关于x的同余方程ax≡1(modb)的最小正整数解。输入输入文件为mod.in。输入只有一行，包含两个正整数a,b，用一个空格隔开。输出输出文件为mod.out。输出只有一行，包含一个正整数x0，即最小正整数解。输入数据保证一定有解。样例输入310样例输出7提示「数据范围」对于40%的数据，2≤b≤1,000；对于60%的数据，2≤b≤50,000,000；对于100%的数据，2≤a,b≤2,000,000,000。代码[crayon-6939338c52f82020964617/] ...
22013年11月7日7,732扩展欧几里得算法