J、智乃的C语言模除方程

这道题就分情况讨论随便算一算就行了。

不过这道题的重点不在于数学计算，而是如何建模。

首先第一个难点,$[l,r][l,r]$,$[L,R][L,R]$区间都是包含数轴正负数轴，这个就很讨厌，所以第一步，首先把所有问题都移动到正半轴$[1,r][1,r]$,$[1,R][1,R]$考虑，见std的主函数部分。

接下来观察题目中所求的东西：统计$x\mathrm{\%}P=Q(Q\in [l,r])\{x\backslash \%P=Q(Q\backslash in[l,r])\}$中$x\in [L,R]x\backslash in[L,R]$的解的个数。

首先定义一个二元函数$f(x,y)=[x\mathrm{\%}P=y]f(x,y)=[x\backslash \%P=y]$，其中中括号$[][\backslash ;\backslash ;]$称为艾弗森括号，当括号内的表达式为真时，值为$1\{1\}$否则为$0\{0\}$。

问题转化成了求${\sum }_{i=L}^R{\sum }_{j=l}^{r}f(i,j)\backslash sum\_\{i=L\}^\{R\}\backslash sum\_\{j=l\}^\{r\}f(i,j)$。

如果用图像来表示的话，本题的模型可以表示为：二维平面上有若干个点，选取一个矩阵，问矩阵中包括了多少个点。

这是啥呢，这不是二维前缀和？

所以令$s(i,j)=su{m}_{i=1}^R{\sum }_{j=1}^{r}f(i,j)s(i,j)=sum\_\{i=1\}^\{R\}\backslash sum\_\{j=1\}^\{r\}f(i,j)$。

所以答案$ans=s(R,r)-s(L-1,r)-s(R,l-1)+s(L-1,l-1)ans=s(R,r)-s(L-1,r)-s(R,l-1)+s(L-1,l-1)$（二维前缀和的容斥，看不懂的话去学一下二维前缀和https://blog.nowcoder.net/n/1f56ba230f0841888738f6c246bfd8f1）

所以问题最终被转化成了最一般的形式，即$s(i,j)s(i,j)$的求法。

同时因为$s(i,j)s(i,j)$的定义都是1到某个数字连续，所以答案肯定是关于P有循环节的，然后其实就除一下模一下就行了。

时间复杂度$O(1)O(1)$，空间复杂度$O(1)O(1)$。

#include<bits/stdc++.h>
using namespace std;
long long _l, _r, _L, _R, P, ans;
long long calcEx(long long x, long long y)
{
	x = min(P - 1, x);
	long long round = (y + 1) / P;
	long long last = (y + 1) % P;
	return (x + 1) * round + min(last, x + 1) - 1;
}
long long calc(long long l, long long r, long long L, long long R)
{
	return calcEx(r, R) - calcEx(l - 1, R) - calcEx(r, L - 1) + calcEx(l - 1, L - 1);
}
int main()
{
	scanf("%lld %lld %lld %lld %lld", &P, &_l, &_r, &_L, &_R);
	P = abs(P);
	if (_l <= 0 && 0 <= _r)
	{
		long long base = ((long long)1e10) / P * P;
		ans += (base + _R) / P - (base + _L - 1) / P;
	}
	if (_R > 0 && _r > 0)
	{
		ans += calc(max(1LL, _l), _r, max(1LL, _L), _R);
	}
	if (_L < 0 && _l < 0)
	{
		ans += calc(max(1LL, -_r), -_l, max(1LL, -_R), -_L);
	}
	printf("%lld\n", ans);
	return 0;
}