C++博客-treeboy

[转载]几道与Gcd有关的题

treeboy — Tue, 26 Jul 2011 13:40:00 GMT

真的是好东西~
(I). POJ 2480 Longge's problem (http://poj.org/problem?id=2480)

题目大意: 求 sigma(gcd(i, n)), 1 ≤ i ≤ n.

考虑到枚举 i 可能会超时, 我们可以反过来枚举 d | n, 那么答案就是 sigma(d * phi(n / d)).

(II). SPOJ LCMSUM (https://www.spoj.pl/problems/LCMSUM/)

题目大意: 求 sigma(lcm(i, n)), 1 ≤ i ≤ n.

sigma(lcm(i, n)) = n * sigma(i / gcd(i, n)). 同上题一样, 枚举 d | n, 问题转化为求 sigma(i), gcd(i, n / d) == 1. 可以发现如果 i 与 n 互质, 那么 n – i与 n 也互质. 将互质的数两两配对后答案就是 n / d * phi(n / d) / 2.

(III). SPOJ GCDEX (https://www.spoj.pl/problems/GCDEX/)

题目大意: 求 sigma(gcd(i, j)), 1 ≤ i < j ≤ n.

枚举 j 后转化为 (I).

(IV). POI Zap (http://www.zybbs.org/JudgeOnline/problem.php?id=1101)

题目大意: 求有多少对 gcd(i, j) == d (i ≤ a, j ≤ b).

令 a’ = a / d, b’ = b / d, 问题等价于求满足 gcd(i, j) == 1的数量 (i ≤ a’, j ≤ b’).

定义 F(k) 为 gcd(i, j) ≥ k 的数量, G(k) 为 gcd(i, j) == k 的数量.

那么F(k) = (a’ / k) * (b’ / k)

根据容斥原理有G(1) = F(1) – F(2) – F(3) - F(5) + F(6) …

系数可以用筛法预处理, 同时观察到对于连续的一段 k, F(k) 都是相同的,可以一起算出来. 通过预处理系数的前缀和可以在 O(sqrt(n)) 的时间算出 G(1).

(V). SPOJ PGCD (https://www.spoj.pl/problems/PGCD/)

题目大意: 求有多少 gcd(i, j) 是质数, 1 ≤ i ≤ a, 1 ≤ j ≤ b.

枚举质数 P 后转化为 (IV).

(VI). NOI 2010 能量采集 (http://www.zybbs.org/JudgeOnline/problem.php?id=2005)

题目大意: 求 sigma(gcd(i, j)), i ≤ a, j ≤ b.

Sol 1.

令 F[k] 为满足 gcd(i, j) == k 的数量.

那么F[k] = (a / k) * (b / k) – F[2k] – F[3k] – F[4k] …

答案就是 sigma(i * F[i]).

时间复杂度 O(n / 1 + n / 2 + n / 3 + …) = O(nlogn).

Sol 2.

枚举 d = gcd(i, j), a’ = a / d, b’ = b / d, 那么问题转化为求满足 gcd(i, j) == 1(i ≤ a, j ≤ b) 的数量, 也就转化为 (IV), 将这个数量记为 F(a, b).

同时注意到对于一段连续的d, F(a’, b’) 都是一样的, 可以一起算出来.

时间复杂度 O(sqrt(n) * sqrt(n)) = O(n).

(VII). Crash 的数字表格 (http://www.zybbs.org/JudgeOnline/problem.php?id=2154)

题目大意: 求 sigma(lcm(i, j)) (i ≤ a, j ≤ b).

sigma(lcm(i, j)) = sigma(i * j / gcd(i, j))

枚举 d = gcd(i, j), 我们只需要对于所有相同的 d, 计算出 sigma(i * j).

令 a’ = a / d, b’ = b / d, 那么问题转化为求 F(a’, b’) = sigma(i * j) (gcd(i, j) == 1, i ≤ a’, j ≤ b’).

令 Sum(a, b) = 1 * 1 + 1 * 2 + … + a * b, 由等差数列的求和公式可得:

Sum(a, b) = a * (a + 1) * b * (b + 1) / 4.

根据容斥原理有F(a, b) =1² * Sum(a / 1, b / 1) - 2² * Sum(a / 2, b / 2) - 3² * Sum(a / 3, b / 3) - 5² * Sum(a / 5, b / 5) + 6² * Sum(a / 6, b / 6)..

注意到对于一段连续的 i, Sum(a / i, b / i) 是相同的, Sum 的系数也可以通过筛法预处理出来.

最后, 对于一段连续的 d, F(a’, b’) 也是相同的, 可以一起算出来.

时间复杂度 O(sqrt(n) * sqrt(n)) = O(n).

扩展阅读

线性筛法: http://www.cppblog.com/sdfond/archive/2009/03/16/76775.html

四道Gcd统计问题: http://hi.baidu.com/广陵lonely散/blog/item/6b00f8de2ca366b7cd11669e.html

treeboy 2011-07-26 21:40 发表评论

八中OJ

treeboy — Tue, 21 Jun 2011 02:49:00 GMT

[Sdoi2011]工作安排: 规模不大,工作安排.很容易想到费用流,由于愤怒函数单调增,所以直接连边.费用作差
[Sdoi2011]消耗战: 很综合的一道题.可以看出来是树中的最小割.两种做法:1)增加一个汇点,将每个询问定点连汇,容量INF.实现好的link_cut tree维护最大流能跑过去.2)直接思维的话去掉的边肯定是一些点的LCA到根的最小值.那么就把所有的点分组.用动态规划去做(单调栈维护)

2011.7.14多做题,多思考>_<

[2010国家集训队]拉拉队排练:找前k长的奇数长的回文串的乘积.这是一个很经典的后缀数组维护的题目,但是学习了twb神牛的神扩展kmp解法.(回来用后缀数组写一个^_^)

[2010国家集训队]布娃娃:给定一坨区间,找符合该区间的第k大值.添加事件点,用一棵平衡树维护每个布娃娃的魅力值.
2010.7.25从数学夏令营回来,晋级问题不大
[2010国家集训队]稳定婚姻:先写了一个暴力网络流,然后总结增广路的形式,膜拜我校的小同学

treeboy 2011-06-21 10:49 发表评论

Tyvj做题记录

treeboy — Tue, 07 Jun 2011 13:56:00 GMT

[CPU监控] 线段树的好题.先考虑PQA和CQA的做法."标记域是用来总结一段操作序列","逢下传必更新".
[序列划分] 直接O(N)贪心.很容易想到
[菌落计算] 扫描线+线段树维护.利用前缀和的思想计算答案.要离散化
[计算机检修] heap
[航线导航] POJ的原题(鸣谢:Foreverbell).设F[s][c]在s点有c的最小花费.维护这个东西就可以了

treeboy 2011-06-07 21:56 发表评论

SPOJ做题记录

treeboy — Sun, 29 May 2011 06:08:00 GMT

GSS1:给定一个序列,要求求出一个区间[l,r]中最大的子段和.维护一棵线段树,记录每个子区间的总和,从左边连续的最大和,右边连续的最大和,区间的最大子段和.查询的时候要注意转移细节.

COURIER:状态压缩的动态规划.f[S][Bx]表示人已经完成了S集合中的任务,当前在任务x的结束位置Bx时的mindist.
f[S|(1<

treeboy 2011-05-29 14:08 发表评论