2020-2021:teams:famerwzyyuki:week_11_2020_7_31-2020_8_7
这是本文档旧的修订版！
吴湛宇
专题
数论
比赛
本周推荐题目
有n个数，求\(\sum_{i=1}^n \sum_{j=i+1}^n (a_i a_j\bmod\,200003) \)
利用原根将每个数转化为\(g^x\)的形式
这样两数相乘就变成了指数相加
统计每个\(g^x\)出现的次数 用fft把这个数组自己乘一下 即可得出任意两数相乘后每个\(g^x\)出现的次数
最后减去\(\sum_{i=1}^n (a_i^2\bmod\,200003)\)再除以2就是答案了
2020-2021/teams/famerwzyyuki/week_11_2020_7_31-2020_8_7.1597374964.txt.gz · 最后更改: 2020/08/14 11:16 由 wzy2001wzy
