台湾菜

数论专题

twcai • acm/icpc

要开数论专题了,发一篇日志报告做题进度来督促自己。
知识点:
独立剩余

进位制: 进位制非常强大,在两个64位整数之间运算并取模的过程中,可以防止溢出(不需要动用大数),而且复杂度比较低。
来看乘法运算和幂运算。设x, y , n是三个long long 的整数,我们需要分别计算 [math](x * y) % n[/math] 和 [math](x ^ y) % n[/math] .
首先是乘法,把 y 转化成二进制,[math]y = sum{i = 0}{k}{a_i * 2 ^ i}[/math] , 那么 [math]x * y = sum{i = 0}{k}{(x * a_i * 2 ^ i) % n}[/math] . 因为[math]a_i[/math]的取值只有0 和 1, 所以这个计算的过程被大大简化了。
幂运算基本做法相同,[math]x ^ y = prod{i = 0}{k}{(x * a_i * 2 ^ i) % n}[/math] , 在幂运算计算过程中 [math]x * a_i * 2 ^ i[/math] 可以由前一个推得,并且需要使用到乘法运算。

Update : 本来看数论就是因为受了宁波理工A题的刺激,今天在黄队的读书笔记上终于找到这个知识点 “独立剩余”

POJ:
1006
5099752 clumsydragon 1006 Accepted 392K 32MS G++ 844B
中国剩余定理
1061
5082504 clumsydragon 1061 Accepted 400K 16MS G++ 870B
扩展欧几里德算法解线性方程 : [math]A * (m - n) + V * L = y - x (m > n)[/math]
结果就是大于0的第一个解 [math]A_i * (y - x) / {gcd(m - n, L)}[/math]
1405
1423
5090074 clumsydragon 1423 Accepted 8236K 282MS G++ 699B
使用公式 [math]n! = sqrt{2 * n^2} * (n/e)^n * (1 + 1/(12*n) + 1/(288* n^2) + O(1/n^3))[/math]
据说是《计算机程序设计艺术》中的一个公式,好强大。
1606
1811
Miller_Rabin + 快速幂取模 + Pollard的rho启发式整数因子分解
1845
2447
2700
3146
3219
3358

HDOJ:
1930
1348734 2009-05-08 13:57:06 Accepted 1930 0MS 268K 1182 B G++ CD@HDU
比较单纯的中国剩余定理

comments powered by Disqus