AC. 梦想

frank_c1

GCD黑科技

发布于2016年03月25日 | 暂无评论 | 3,552阅读 | 数论

来看这样一个问题:

T组询问,第i组询问给出两个正整数a_i,b_i。对于每组询问,求\gcd(a_i,b_i)1 \le T \le 10 ^ 7,1 \le a_i,b_i \le 10 ^ 7

对于一般题目,求一次\gcd(a,b)的时间是\log(n)。但是,在可以预处理的情况下,即a,b是两个在一定范围内的整数时,求\gcd的过程可以进一步加速。设a,b \in [1,n],考虑如下结论:

1.\gcd(a,b) = \gcd(a,b \% a),则当a \le \sqrt{n}时,可以通过预处理[1,\sqrt{n}]\gcd达到询问O(1)

2.设p是质数。若p|a,则\gcd(p,a) = p,否则\gcd(p,a) = 1

3.对于一个正整数k,总是可以将k分解成三个正整数相乘的形式,令k = k_1 k_2 k_3,要求k_i满足k_i \le \sqrt{n},或k_i是质数。对于询问a,b,我们用a的分解式a = a_1 a_2 a_3分别计算a_i\gcd(a,b)的贡献,若a_i \le \sqrt{n},用结论1求;若a_i是质数,用结论2求。如求\gcd(40,60),可令40 = 2 \times 4 \times 5;有d_1 = \gcd(2,60) = 2d_2 = \gcd(4,60/d_1) = 2d_3 = \gcd(5,60/(d_1 d_2)) = 5,故\gcd(40,60) = d_1 d_2 d_3 = 2 \times 2 \times 5 = 20

根据以上结论,我们需要维护两种数据结构。

1.\gcd(a,b) \; (a,b \in [1,\sqrt{n}])

2.a的分解式a = a_1 a_2 a_3 \; (a \in [1,n])

对于第一部分,我们可以考虑暴力求,但是这样的复杂度是O(n \log n)的。由于f_k(i) = \gcd(k,i)是积性函数,所以我们可以线性筛,复杂度O(n)

对于第二部分,对于正整数a,设pa的最小质因子,k = \frac{a} {p},则可以用k的分解式的较小项乘上p得到a的分解式。这个过程恰好可以用线性筛完成,复杂度O(n)

所以问题就可以在O(n + T)的复杂度解决啦。论文链接

有了黑科技,自然就会出现一些既卡空间又卡时间的丧心病狂题目——BZOJ4454。居然伪装成C语言练习题,谁信?