F(n) = 0 mod m 等同于 n mod m - k*k mod m = 0. n mod m 只能取 [0, m-1]，用 m 个loop，只需考虑k。
代码：
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define CHECKTIME() printf(%.2lf , (double)clock() / CLOCKS_PER_SEC) /*************** Program Begin **********************/ //long long bestK[1000]; class SparseFactorialDiv2 { public: // 计算 [0, uppderbound] 区间内，模divisor值为 d 的数的个数。 long long getC(long long upperbound, long long divisor, long long d) { if (upperbound % divisor >= d) { return upperbound / divisor + 1; } else { return upperbound / divisor; } } // 计算 区间 [0, upperbound] 内，F(n) % divisor == 0 的数的个数。 long long calc(long long uppperbound, long long divisor) { long long res = 0; vector bestK(divisor, -1); for (long long k = 0; k * k < uppperbound; k++) { // 找的最小的k, 使 k * k % divisor == d if (bestK[ (k * k) % divisor ] == -1) { bestK[ (k * k) % divisor ] = k; } } for (int d = 0; d < divisor; d++) { if (bestK[d] == -1) { continue; } res += ( getC(uppperbound, divisor, d) - getC(bestK[d] * bestK[d], divisor, d) ); } return res; } long long getCount(long long lo, long long hi, long long divisor) { return calc(hi, divisor) - calc(lo - 1, divisor); } }; /************** Program End ************************/