看标题,不敢说是题解,因为我不敢保证正确哈
首先给vfleaking、jcvb、Picks、ydc等神犇的做法跪了
我发现a[i]很大,于是想到要对大质数取模,O(nm),极限数据1.68s。试着常数优化但是无效(可能我不会常数优化)
于是我找一个比较小的质数(30000到40000),在模这个质数p意义下计算[1,p-1],如果某个x答案不为0,然后把m以内mod p余x的数筛掉,这样复杂度是O(pn+m),但是有可能会错…
于是我找了5个(好像是6个,我不记得了)质数去筛,把剩余的数直接输出,这样正确率貌似提高了,时间复杂度是O(kpn),由于开了 long long 所以极限数据0.5s。
也许能过或者得一些分吧(不过考完有人跟我讲出题人可以把50000以内质数全部卡掉……似乎滚粗了呵呵)