K、智乃的C语言模除方程(another version)

首先可以按照上一道题的做法去做（直接改上一题的calcEx即可），但是实际上这道题在思维上更简单了，不需要转化成二维前缀和。

首先你要知道一个叫做整除分块的数论板子。

整除分块是处理形如$\frac{N}{i}\backslash frac\{N\}\{i\}$，其中$ii$为循环变量，为什么叫他分块呢，是因为对于形如$\frac{N}{i}\backslash frac\{N\}\{i\}$的式子，对于$i\in [1,N]i\; \backslash in\; [1,N]$只有$\sqrt{N}\backslash sqrt\; N$种结果。

然后模除可以改写成一次除法+一次减法的形式，即$a\mathrm{\%}b=a-\lfloor \frac{a}{b}\rfloor \ast ba\backslash \%b=a-\backslash left\; \backslash lfloor\; \backslash frac\{a\}\{b\}\; \backslash right\; \backslash rfloor*b$

这个也是一个经典套路，但凡你碰到$N\mathrm{\%}iN\backslash \%i$这个东西要循环枚举$ii$的时候你就可以把它变成$N\mathrm{\%}i=N-\lfloor \frac{N}{i}\rfloor \ast iN\backslash \%i=N-\backslash left\; \backslash lfloor\; \backslash frac\{N\}\{i\}\; \backslash right\; \backslash rfloor*i$，然后尝试整除分块。

对于本题，$P\mathrm{\%}x=Q(Q\in [l,r])\{P\backslash \%x=Q(Q\backslash in[l,r])\}$首先把它变形为$P-\lfloor \frac{P}{x}\rfloor \ast x=Q(Q\in [l,r])\{P-\backslash left\; \backslash lfloor\; \backslash frac\{P\}\{x\}\; \backslash right\; \backslash rfloor*x=Q(Q\backslash in[l,r])\}$，然后在整除分块的过程中$\lfloor \frac{P}{x}\rfloor \backslash left\; \backslash lfloor\; \backslash frac\{P\}\{x\}\; \backslash right\; \backslash rfloor$就是常数，令其等于$cc$。

原式等于$P-c\ast x=Q(Q\in [l,r])\{P-c*x=Q(Q\backslash in[l,r])\}$，把左侧的$P-c\ast xP-c*x$看成是一个等差数列。

问题转化成求一个等差数列的第$LL$项到第$RR$项中有多少项的值在$ll$到$rr$范围内，显然满足条件的是$LL$项到第$RR$项中连续的某一段，直接$O(1)O(1)$计算即可。

时间复杂度$O(\sqrt{P})O(\backslash sqrt\; P)$，空间复杂度$O(1)O(1)$。

#include<bits/stdc++.h>
using namespace std;
long long _l, _r, _L, _R, P, ans;
long long segment_intersect(long long S1, long long T1, long long S2, long long T2)
{
	long long S = max(S1, S2);
	long long T = min(T1, T2);
	return max(0LL, T - S + 1);
}
long long cal(long long a, long long d, long long base, long long len)
{
	if (d == 0)
	{
		return _l <= a && a <= _r ? segment_intersect(_L, _R, base, base + len) + segment_intersect(_L, _R, -base - len, -base ) : 0;
	}
	long long s = a > _r ? (a - _r + d - 1) / d : 0;
	long long t = a >= _l ? (a - _l) / d : -1;
	t = min(t, len - 1);
	return segment_intersect(_L, _R, base + s, base + t) + segment_intersect(_L, _R, -base - t, -base - s);
}
int main()
{
	scanf("%lld %lld %lld %lld %lld", &P, &_l, &_r, &_L, &_R);
	if (P < 0)
	{
		P = -P;
		_l = -_l;
		_r = -_r;
		swap(_l, _r);
	}
	_l = max(_l, 0LL);
	for (long long l = 1, r; l <= P; l = r + 1)
	{
		r = P / (P / l);
		long long a = P % l;
		long long d = P / l;
		ans += cal(a, d, l, r - l + 1);
	}
	ans += cal(P, 0, P + 1, 1000000000);
	printf("%lld\n", ans);
	return 0;
}