CVBB ACM Team

当场过题情况：
A:思路&代码：Yuki
B:思路&代码：Wzy
C:
D:思路&代码：Wzy
E:
F:思路&代码：Wzy
G:思路&代码：Yuki
H:
I:思路&代码：Yuki
J:
K:思路：Yuki&Famer 代码：Yuki
L:
M:
N:思路&代码：Famer

A： 题意：给出一个n，然后给出n个名字、颜色、分数，然后给出5个奖励名字和一个奖励颜色，从n个中选择5个，选出的5个名字不重复，如果出现一个奖励名字，则获得10%的总评分数，出现一个奖励颜色，则获得20%的总评分数，求最大的总评分数。
思路：因为每个名字只能选一个，将卡片按名字分类，只能选5张卡片，加成最多为150%

B：签到题
D：
计算 $$\sum_{a_i\le m} \big[ (\gcd(a_1,\cdots,a_n)==d)\prod_{j=1}^n a_j^k\big]$$
其中 $$m,d\le 10^5,n\le 10^{100000} ,k\le 10^9$$
解：设$$r=\left \lfloor \frac{m}{d} \right \rfloor $$ 则原式等于 $$d^{nk} \sum_{a_i\le r} \big[(\gcd(a_1,\cdots,a_n)==1)\prod_{j=1}^n a_j^k\big]$$ 反演一下得 $$d^{nk}\sum_{d_0=1}^r \mu(d_0) \sum_{a_i\le r,d_0|a_i}(\prod_{j=1}^n a_j^k)$$ 根据对称性 $$ \sum_{a_i\le r,d_0|a_i}(\prod_{j=1}^n a_j^k)=d_0^{nk}(\sum_{j=1}^\left \lfloor \frac{r}{d_0} \right \rfloor j^k)^n$$ 所以就是要求$$d^{nk}\sum_{d_0=1}^r \mu(d_0)d_0^{nk}(\sum_{j=1}^\left \lfloor \frac{r}{d_0} \right \rfloor j^k)^n$$ 由于n只在指数上出现，可以用$$a^{\phi(p)} \equiv 1 \pmod{p}$$ 把n干掉 再处理一下\(j^k\)的前缀和
就可以求了
最后吐槽一下 这道题的模数p居然不是个质数！！！！！

F：
计算$$\sum_{a=2}^n \bigg( a\sum_{b=a}^n \left \lfloor \log_{a} b \right \rfloor \left \lceil \log_{b} a \right \rceil \bigg)$$ 其中\(n\le 10^{12}\)
解：显然，\(\left \lceil \log_{b} a \right \rceil =1\)
当\(a\le \sqrt{n}\)时: \(\left \lfloor \log_{a} b \right \rfloor\)至多有\(\log n\)种取值，枚举即可
当\(a> \sqrt{n}\)时: \(\left \lfloor \log_{a} b \right \rfloor=1\) 可以直接求和