2020-2021:teams:farmer_john:2020暑假精选题目:数学
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:farmer_john:2020暑假精选题目:数学 [2020/12/24 20:06] jjleo [题解] |
2020-2021:teams:farmer_john:2020暑假精选题目:数学 [2020/12/24 20:07] (当前版本) jjleo [题解] |
||
|---|---|---|---|
| 行 17: | 行 17: | ||
| 给出一个长度为$n$的序列$a_i$，求$$\sum_{\gcd(a_{p_{1}},a_{p_{1}},\cdots,a_{p_{k}}) \ne 1}k \cdot \gcd(a_{p_{1}},a_{p_{1}},\cdots,a_{p_{k}}) \pmod{10^9+7}$$其中$1 \le k \le n, p_1<p_2< \cdots < p_k$。$(n \le 2 \times 10^5, a_i \le 10^6)$ | 给出一个长度为$n$的序列$a_i$，求$$\sum_{\gcd(a_{p_{1}},a_{p_{1}},\cdots,a_{p_{k}}) \ne 1}k \cdot \gcd(a_{p_{1}},a_{p_{1}},\cdots,a_{p_{k}}) \pmod{10^9+7}$$其中$1 \le k \le n, p_1<p_2< \cdots < p_k$。$(n \le 2 \times 10^5, a_i \le 10^6)$ | ||
| ====题解==== | ====题解==== | ||
| - | 上一题的升级版，我们在上一题我们通过容斥求出了$$f_i=\sum_{\gcd(a_{p_{1}},a_{p_{1}},\cdots,a_{p_{k}}) = i}1$$本题我们则需要求出$$g_i=\sum_{\gcd(a_{p_{1}},a_{p_{1}},\cdots,a_{p_{k}}) = i}k$$ 最终答案为 $$\sum_{i=2}^{n}ig_i$$ 类似上一题的方法设$$cnt_i=\sum_{j=1}^n[i|a_j]$$则$$g_i=\sum_{j=1}^{cnt_i}j\binom{cnt_i}{j}-\sum_{j=1}^ng_j[i|j]$$ $$=\sum_{j=1}^{cnt_i}\frac{(cnt_i)!j}{j!(cnt_i-j)!}-\sum_{j=1}^ng_j[i|j]$$ $$=cnt_i\sum_{j=1}^{cnt_i}\frac{(cnt_i-1)!}{(j-1)!(cnt_i-j)!}-\sum_{j=1}^ng_j[i|j]$$ $$=cnt_i\sum_{j=0}^{cnt_i-1}\binom{cnt_i-1}{j}-\sum_{j=1}^ng_j[i|j]$$ $$=cnt_i \cdot 2^{cnt_i-1}-\sum_{j=1}^ng_j[i|j]$$ 逆序枚举$i$即可$O(n \log n)$求解。 | + | 上一题的升级版，我们在上一题我们通过容斥求出了$$f_i=\sum_{\gcd(a_{p_{1}},a_{p_{1}},\cdots,a_{p_{k}}) = i}1$$本题我们则需要求出$$g_i=\sum_{\gcd(a_{p_{1}},a_{p_{1}},\cdots,a_{p_{k}}) = i}k$$ 最终答案为 $$\sum_{i=2}^{n}ig_i$$ 类似上一题的方法设$$cnt_i=\sum_{j=1}^n[i|a_j]$$则$$g_i=\sum_{j=1}^{cnt_i}j\binom{cnt_i}{j}-\sum_{j=1}^Ng_j[i|j]$$ $$=\sum_{j=1}^{cnt_i}\frac{(cnt_i)!j}{j!(cnt_i-j)!}-\sum_{j=1}^Ng_j[i|j]$$ $$=cnt_i\sum_{j=1}^{cnt_i}\frac{(cnt_i-1)!}{(j-1)!(cnt_i-j)!}-\sum_{j=1}^Ng_j[i|j]$$ $$=cnt_i\sum_{j=0}^{cnt_i-1}\binom{cnt_i-1}{j}-\sum_{j=1}^Ng_j[i|j]$$ $$=cnt_i \cdot 2^{cnt_i-1}-\sum_{j=1}^Ng_j[i|j]$$ 逆序枚举$i$即可$O(n \log n)$求解。 |
2020-2021/teams/farmer_john/2020暑假精选题目/数学.1608811606.txt.gz · 最后更改: 2020/12/24 20:06 由 jjleo
