TopCoder SRM596: SparseFactorialDiv2

\(F(n) = n (n - 1^2) (n - 2^2) ... (n - k^2)　\) ただし \(k\) は \((n - k^2) > 0\) となる最大の整数とする

「\(F(n) \mod m = 0 \)」が成立することと

「\((n - x^2) \mod m = 0\) かつ \( n > x^2 \) となるような自然数 \( x \) が存在すること」は同値になる。

ここで「\(F(n + m) \mod m = 0 \)」の条件を考えると、同様な手順で

「\((n - x^2) \mod m = 0\) かつ \( n + m > x^2 \) となるような自然数 \( x \) が存在すること」となり、前者の条件には全く違いで出てこない。そして後者の条件についても \( n > x^2 \) から \( n + m > x^2 \) へと緩くなっていることから、
「\(F(n) \mod m = 0 \)」ならば「\(F(n + m) \mod m = 0 \)」ということが言える。

したがって、0 から m-1 までの整数 k についてそれぞれ \(F(i * m + k) \mod m = 0 \)」となるような最小を i を見つければ、 \(F((i + j) * m + k)\)（j は自然数）について全て m で割り切れるため、あとは範囲内のものを数え上げるだけになる。

public class SparseFactorialDiv2 {
    public long solve(long x, long divisor) {
        long ans = 0;
        for (int m = 0; m < divisor; m++) {
            long t = 0;
            bool found = false;
            for (long p = m; p <= x; p += divisor) {
                if (!found) {
                    while (t < divisor && t * t < p) {
                        if (p % divisor == t * t % divisor) {
                            found = true;
                            break;
                        }
                        t++;
                    }
                    if (t >= divisor && !found) break;
                }
                if (found) {
                    // F(p + i * divisor) where i >= 0 are all divisible
                    ans += (x - p) / divisor + 1;
                    break;
                }
            }
        }
        return ans;
    }

    public long getCount(long lo, long hi, long divisor) {
        return solve(hi, divisor) - solve(lo - 1, divisor);
    }
}