2021牛客暑期多校训练营1 H. Hash Function（数论，FFT/NTT卷积）
Hash Function
https://ac.nowcoder.com/acm/contest/11166/H
Description
给出一个序列，找到最小的正整数 ，使得
能够让序列在函数的作用后互不相同。
Solution
不妨思考什么时候会存在两个数字 满足
：
设 ，由同余的性质，得到
，即
，因此满足
于是我们知道， 的取值不能够是
的因子。
那么只需要找到序列中所有的 即可，显而易见的就是借助卷积。
不妨思考我们如何使用卷积计算 ？显而易见的，类比
的卷积，我们可以用一个桶来表示这个数字是否存在，令
这样的话，卷积结果
为1。再看到本题需要计算
，因为
是负数难以表示，先让他偏移一个值
，最后再减回来就好了。
注意特判 的时候结果为
。
Code
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48636569
一些比赛的题解 文章被收录于专栏
一些比赛的题解
查看19道真题和解析