算法竞赛中一类有关最大公因数 gcd 的求和问题

本文原载于 Math | UESTC_Jungle

如果遇到这样一类求和

T = \sum_{A \subseteq S}{(a_1, a_2, \dots, a_n, k_1, k_2, \dots, k_m) \cdot f(A)}

其中 a_i 是集合 A 里的元素,k_j 是额外需要求 gcd 的元素. 记 K = k_1k_2\cdots{}k_m.

可以枚举 gcd,转换为

T = \sum_{d|K}{\left(d \cdot \sum_{A \subseteq S}{[d = (a_1,a_2,\dots,a_n, k_1, k_2, \dots, k_m)]\cdot{}f(A)}\right)}

继续阅读“算法竞赛中一类有关最大公因数 gcd 的求和问题”

ZOJ 3806 – Incircle and Circumcircle 解题报告

这是我写的第一篇解题报告,在此有必要说明一下为什么决定写这一篇解题报告。

这道题是我在集训队 Div.2 训练赛中第一次做出的一道全场只有唯一一个人过的题,也是我过的第一道防 ak 题。就想写个解题报告纪念一下。题目很简单,希望大佬们不要嘲笑我。

题意是这样的,给出三角形的内切圆半径 r 和外接圆半径 R,判断是否存在可能的三角形三边长并输出。

这题能过也有运气成分,主要是在思考的时候突然想到了用角度来算边。

继续阅读“ZOJ 3806 – Incircle and Circumcircle 解题报告”