首页 > 代码库 > 一周总结4

一周总结4

         一周总结

数论

POJ3058 题意:就是给定一个分数,要求把它化成二进制形式,求最小的循环节和循环节开始的位置。

首先约分化成最简分数形式p/q,然后化成二进制就是每次乘2大于1时,本位为1,该数取余,那么总会存在。则(p*2^i)%q=(p*2^j)%q,这里假设i<j,则可化为(p*2^(j-i))%q=1%q

因为gcd(p,q)==1,2^(j-i)%q=1%q;这时就会想到欧拉公式,枚举q%2^(j-i)的欧拉函数值的因子就行了。

POJ3696 题意:给定一个数字L,问是否存在一个长度为n,且数字全为8的数字,使这个数字能够整除L

首先我们设这个数为(10^n-1)*8/9=m*L,则这个式子可化为(10^n-1)*8=m*L*9;则记gcd(8,9*L)=r,(10^n-1)*8/r=m*9*L/r;所以可得(9*L/r)%(10^n-1)==0,则令y=9*L/r,

10^n-1=d*y;10^n==1(%y)此时gcd(10,y)==1,有解,否则没解,有解时枚举phi(

y)所有的约数即可。

lightOJ 1045 k进制阶乘的指数,化对数求解即可

lightOJ 1236 求一定范围内的最小公倍数的和,用欧拉定理求出互质的数

Dp

做了一些零碎的dp

Hdu 4293 

Hdu 4283

Hdu 2296(AC自动机+dp)

BZOJ 1237

BZOJ 1037

openOJ 2045

Hdu  4563(枚举背包)

Hdu 4562 (关键几何处理)

Hdu 4558

lightOJ 1329(关键是对组合的理解)

 

一周总结4