TopCoder SRM 596 Div2

第3题解题报告

类型：数论 难度：2

题意：给出lo,hi,div三个数，定义函数 F(n) = (n - 0^2) * (n - 1^2) * (n - 2^2) * (n - 3^2) * ... * (n - k^2)

k是满足n-k^2>0的最大整数。

求在[lo,hi]区间内满足F(n)能被div整除的数的个数。

分析：直接遍历[lo,hi]的所有数并判定F(n)能否被div整除不可行，应为hi-lo的数量级在10^12。

这里想到计算素数的**（从小到大找素数，将素数的整数倍标记为非素数），考虑若F(n)能被div整除，那么F(n)的因式 (n-k^2)，0<=k<√n 必定至少有一个能被div整除，也就是说 n-y^2 = divx，所以考虑 divx+y^2，x>=1，y>=0 这个式子的值，如果这个式子的值落在[lo,hi]区间，那么这个数就是满足要求的。那么，遍历x,y，将落在区间内的值加入一个结果set集保证不重，最后统计set的大小就是结果。但是复杂度仍高，考虑当div=2时，复杂度为10^12 * 10^6，显然不能接受。一定把复杂度降低到10^6。

考虑简化上一种方法，由于外层循环是遍历x，寻找落在区间内的 divx +y^2，那么若能知道每个 [divx,div*(x+1)) 区间内的合法的n的个数，那么再乘以x落在区间内的可能值，就能在O(1)算出结果。运用这个思路，再进一步细化，并注意边界条件。

设rc[i]表示 y^2 % div = i 时，y^2 / div 的值再加1，表示这个余数最开始在div的第几个倍数中出现。遍历所有的y，1<=y<√hi，得到rc数组的值。

再计算rc数组中出现的余数的数目cnt，即每div个数有多少个满足条件。再计算所有rc数组的最大值st，即从div的第几个倍数开始，后续的每div个数都一定有cnt个满足要求的数。

之后就是考虑lo，hi两个数的边界条件，记录[lo,divleft)区间和[divright,hi]区间内满足要求的数的个数，left取满足divleft >=lo的最小值，right取满足divright<=hi的最大值

再然后，考虑此时的left和st的关系，若left<st，则此时每div个数符合要求的数还不到cnt个，需遍历rc数组，递增left，直到left=st。

之后就可以计算[left,right]区间内的符合要求的个数，即cnt*(right-left)。