以下题解仅供学习参考使用

抄襲、复制题解，以达到刷AC率/AC数量或其他目的的行为在洛谷是严格禁止的。

洛谷非常重视学术诚信此类行为将会导致您成为作弊者。具體细则请查看

首先，蒟蒻的我要先膜一下机房的诸位dalao

前情提要：下午dyx dalao讲数论然而我太弱了只听懂这一道

此题考点为抽屉原理+背包

把多於n+1个的物体放到n个抽屉里，则至少有一个抽屉里的东西不少于两件

代入本题中我们可以发现，当得到这个序列的n个前缀和%m时一定会出現两个相同的数，这两个前缀和相减得到的序列和一定可以被m整除因此，当n>m时我们可以特判为序列和一定可以被m整除从而将n的范围从1e6縮小到1e3。

特判后n和m的数据范围都是1e3，n方可过直接用简单的背包dp即可求解。

首先，我们发现n的范围非常大m在1000以内。

我们知道n>=m时，一定有一段数字和能被m整除

所以，讨论n<m的情况n在1000以内。

背包dp[i][j]表示前i个数中取，和除以m余数为j的

最后%出题人和楼下神仙！

一个简单的类似于筛法的算法

先对输入嘚数取模，然后计算取模后每个数的个数

然后用类似素数筛法的思想标记当前数i能新组成的数有多少

如果你认为某个题解有问题欢迎向洛谷反馈，以帮助更多的同学

请具体说明理由，以增加反馈的可信度