UVA 11549 Calculator Conundrum

题意

给出一个数,你要对他反复平方,平方完之后总是取运算结果的前n个十进制位(如果结果大于n位)作为答案,然后对这个答案继续进行刚才的操作。

这是一个循环的过程,你要找出在这个循环节中最大的数。

思路

首先是循环节这一点,意识到形成循环节并不难。从理论上来证明:我们可以设定一个运算#表示相乘取前n位这一操作,初始值为a,a#1=a,1为单位元,N为所有k及k位以下整数组成的集合,两个数做运算得到的结果必然属于N,则<N,#>构成一个有限群,<a^x>必然构成循环群。

取前n位这一操作可以用字符串流,但是那样常数非常大,所以还是考虑利用数学运算来实现,这样会提高速度。

找出循环节的方法有两种,一种是开一个set,算一次insert一次,如果碰到算过的就停下。还有一种是Floyd判圈法,也就是同时维护两个数A和B,每一次令A=A^2,B=B^3,也就是B总是会比A多走一步,这样如果有环,A和B一定会相遇,在相遇时停下。

代码

Floyd判圈法,数学方法求前n位。

 

Codeforces 515B Drazil and His Happy Friends

题意

Translated by paryerhgq

Drazil有很多朋友,他们中有些人是快乐的,有些人是不快乐的。 Drazil想让他的朋友变得快乐。于是,他发明了以下的计划。
在他的朋友中,有n个男孩和m个女孩。我们把男孩从0到n-1编号,女孩从0到m-1编号。在第i天,Drazil邀请第i mod n个男孩和第i mod m个女孩一起吃饭(注意i从0开始)。如果两个人之中有一个是快乐的,那么另外一个也会变得快乐,否则,这两个人的心情状态不会改变。一个人一旦成为快乐的人(或者他原本就是快乐的),他能保持永远快乐。
Drazil想知道他是否可以使用该计划,使得他所有的朋友都变得快乐。

思路

注意到问题规模比较小,所以我们直接模拟就好了但是我们要至少操作2*nm次才可以。

有一种不暴力的解法,我们发现我们最后能够变快乐的人的编号x一定满足x = a (mod gcd(boy,girl)),其中boy是男生人数,girl是女生人数,a是某个一开始就快乐的人的编号,这样我们只要扫一遍所有快乐的人,在模gcd(boy,girl)的完全剩余系里标记一下就搞定了。

代码

暴力:

数学:

 

ZOJ 3254 Secret Code

题意

求小于等于M的数中有多少个可以使得A^x=B(mod C)成立。

思路

首先利用extended BSGS求出最小的x使得A^x=B(mod C)成立。

接下来我们要求出最小的len使得A^(x+len*k)=B(mod C),我们知道模C的指数循环节是Phi(C),对于某个特定的幂的最小循环节则一定是Phi(C)的约数。我们要枚举Phi(C)的各个素因数,不断试除试算,知道得到最小的循环节长度len。

得到了x和len之后,答案就是(M-x)/len+1。

代码

 

SPOJ MOD Power Modulo Inverted

题意

求最小的x使得A^x=B(mod C)。

思路

HDU 2815 Mod TreePOJ 3243 Clever Y完全一致,extended BSGS的模板题。

代码

 

HDU 2815 Mod Tree

题意

题目翻译好之后实际上是求解最小的x使得A^x=B(mod C)成立,C不保证是素数。

思路

典型的Extended BSGS模板题。

需要注意的是,内存空间比较紧张,HASH空间不宜开得太大,需要牺牲一些时间换空间。

代码

 

POJ 3243 Clever Y

题意

求解最小的x使得A^x=B(mod C)成立,C不保证是素数。

思路

C不保证素数的BSGS,这时使用扩展BSGS解决,扩展BSGS的实质是在BSGS之前利用这个定理:

Ad=Bd(mod C) <=> A=B(mod C/gcd(C,d))

将问题转化为一般BSGS能够解决的形式,再使用一般BSGS解决。

代码

POJ 2417 Discrete Logging这个问题中也使用了如下exBSGS的代码。

 

POJ 2417 Discrete Logging

题意

求解最小的x使得A^x=B(mod C)成立。数据保证了C一定为素数。

思路

解决这种问题是有一种特定算法Baby Step Giant Step的。BSGS算法的具体思想这里不再赘述。直接套用就可以了。

代码

 

 

HDU 1402 A * B Problem Plus

题意

实现两个大整数的加法

思路

整数加法可以看成多项式加法,然后就可以利用FFT通过进行卷积计算的方法来实现。

浮点数误差不会卡掉这个题。

代码

 

 

POJ 3126 Prime Path

题意

给出你两个四位素数,保证这个素数不会有前导0(也就是1003起跳)。给定一个操作,在只改变一位的前提下,把当前素数变为另一个四位素数(无前导0)。现在问你至少进行多少次这样的操作才能把一个素数变为另一个。

思路

素数的朴素判断需要O(sqrt(n))的时间复杂度,显然不符合本题要求。不妨使用欧氏筛法,在O(n)的时间复杂度内预处理出10000以内的全部素数,之后O(1)时间解决查询某个数是否为素数的问题。

解决完素数问题,剩下的就是近似于求最短路的BFS过程了。具体的实作方法可以参考下面的代码。

代码

 

HDU 1394 Minimum Inversion Number

题意

求环形数组的最小逆序数。

思路

如何求逆序对请参考hdu 1394 求循环串的最小逆序数 暴力法 线段树 归并排序3种方法(hnust_xiehonghao)

本题使用暴力方法也可以通过,但前提是需要知道一个结论:如果是0到n的排列,那么如果把第一个数放到最后,对于这个数列,逆序数是减少a[i],而增加n-1-a[i]的

代码(线段树优化方法)

 

Scroll to top