「ZROI」陈太阳与取模

题目大意：$T$ 次给定 $L,R,A$，请你求出有多少个 $X$ 满足对于任意 $c \in [L,R]$，有 $c \equiv c \mod A \pmod X$

设 $c = k_1x+r$，$c \mod A = k_2x+r$，有

$$c - c \mod A = (k_1-k_2)x$$

即

$$x\ \|\ c - c \mod A$$

那么答案为 $\gcd_{i=L}^{R}(i-i\mod A)$ 的约数个数

可以推出 $gcd$ 只可能是 $A$ 或 $L-L\mod A$

分成 $L<A,L\leq A\leq R,R<A$ 三种情况讨论即可

#include <cstdio>
#include <cmath>

typedef long long LL;

LL read() {
	LL x = 0; char c = getchar();
	while (c < '0' || c > '9') c = getchar();
	while (c >= '0' && c <= '9') {
		x = (x << 3) + (x << 1) + (c ^ 48);
		c = getchar();
	}
	return x;
}

int main() {
	int T = read();
	while (T--) {
		LL L = read(), R = read(), A = read(), G;
		if (R < A) { puts("-1"); continue; }
		if (L <= A && A <= R) G = A;
		if (A < L) {
			if (L - L % A == R - R % A) G = L - L % A;
			else G = A;
		}
		LL M = sqrt(G), ans = 0;
		for (LL i = 1; i <= M; ++i)
			if (G % i == 0) ans += 2;
		if (M * M == G) --ans;
		printf("%lld\n", ans);
	}
	return 0;
}

时间复杂度 $O(T\sqrt A)$