题解：AT_abc402_g [ABC402G] Sum of Prod of Mod of Linear
wwt100127
·
·
题解
第一篇黑体题解，好兴奋
题意
$$
\sum_{i=0}^{N-1} \left[(Ai+B_1) \bmod M \right] \left[ (Ai+B_2) \bmod M \right]
$$
其中 $0 \le A,B_1,B_2 < M$。
## 前置知识
[类欧几里得算法](https://www.luogu.com.cn/problem/P5170)
## 思路
显然 $B_1,B_2$ 等价，不妨设 $B_1 \ge B_2$（否则将两数交换）。
取模比较烦人，所以将原式化成：
$$
\sum_{i=0}^{N-1}
\left[(Ai+B_1) - M \left \lfloor \frac{Ai+B_2}{M} \right \rfloor \right]
\left[(Ai+B_2) - M \left \lfloor \frac{Ai+B_2}{M} \right \rfloor \right]
$$
记
$$
a_i = \left \lfloor \frac{Ai+B_1}{M} \right \rfloor ,b_i=\left \lfloor \frac{Ai+B_2}{M} \right \rfloor
$$
展开后就是：
$$
\sum_{i=0}^{N-1}(Ai+B_1)(Ai+B_2) -
M \sum_{i=0}^{N-1}(Ai+B_1)b_i -
M \sum_{i=0}^{N-1}(Ai+B_2)a_i +
M^2 \sum_{i=0}^{N-1} a_ib_i
$$
第一个可以 $O(1)$ 求出，中间两个算是类欧几里得的板子，我们只需要处理第四个式子就行了。
考虑如何用已知“凑”出 $\sum_{i=0}^{N-1} a_ib_i$。
~~于是你的眼睛无意间扫到了 $0 \le B_1,B_2 < M$ 这个条件~~
也就是说，$(a_i-b_i)$ 的值只能为 $0$ 或 $1$。
那么 $\sum_{i=0}^{N-1} (a_i-b_i)(a_i-b_i-1)= 0$。
展开得：
$$
\sum_{i=0}^{N-1} a_ib_i = \frac{1}{2} \sum_{i=0}^{N-1} (a_i^2+b_i^2-a_i+b_i)
$$
同样可以用类欧几里得解决。
所以最终的答案：
$$
Answer(N-1,M,A,B_1,B_2)= \frac{A^2N(N+1)(2N+1)}{6} + \frac{A(B_1+B_2)N(N+1)}{2} + B_1B_2(N+1)
- M \left [ A \times (h(A,B_1,M,N) + h(A,B_2,M,N)) - B_1 \times f(A,B2,M,N) - B_2 \times f(A,B_1,M,N) \right]
+ \frac{M^2}{2} \left [g(A,B_1,M,N) + g(A,B_2,M,N) - f(A,B_1,M,N) + f(A,B_2,M,N) \right ]
$$
其中：
$$
f(A,B,M,N) = \sum_{i=0}^{N} \left \lfloor \frac{Ai+B}{M} \right \rfloor \\
g(A,B,M,N) = \sum_{i=0}^{N} \left \lfloor \frac{Ai+B}{M} \right \rfloor^2 \\
h(A,B,M,N) = \sum_{i=0}^{N} i \left \lfloor \frac{Ai+B}{M} \right \rfloor
$$
## 代码
```cpp
#include<bits/stdc++.h>
#define int __int128
using namespace std;
bool Beginning;
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define se second
#define fi first
using PII=pair<int,int>;
using PIB=pair<int,bool>;
using PBI=pair<bool,int>;
using PBB=pair<bool,bool>;
using PDI=pair<double,int>;
using PID=pair<int,double>;
namespace Memory_Love{
int read(){ int x=0; bool flag=1; char ch=getchar();
while(ch<'0' || ch>'9'){if(ch=='-') flag=0; ch=getchar();}
while(ch>='0' && ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();} return flag? x:-x;}
template<typename T> void read(T &x){ bool flag=1; x=0; char ch=getchar();
while(ch<'0' || ch>'9'){if(ch=='-') flag=0; ch=getchar();}
while(ch>='0' && ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();} x=(flag? x:-x);}
template<typename T,typename ...Args> void read(T &Re,Args &...Res){read(Re),read(Res...);}
template<typename T> void write(T x,char ch=0){if(x<0) x=-x,putchar('-');
static short s[35],top=-1; do{s[++top]=x%10;x/=10;}while(x);
while(~top) putchar(s[top--]+48); if(ch) putchar(ch);}
int gcd(int a,int b){return b==0? a:gcd(b,a%b);}
int lcm(int a,int b){return a/gcd(a,b)*b;}
} using namespace Memory_Love;
int n,m,a,b1,b2;
struct Node
{
int f,g,h;
Node(int F=0,int G=0,int H=0){f=F,g=G,h=H;}
};
namespace Euclid
{
int Pow2(int x){return x*x;}
Node solve(int a,int b,int c,int n)
{
int f,g,h;
if(a==0)
{
f=b/c*(n+1);
g=Pow2(b/c)*(n+1);
h=b/c*n*(n+1)/2;
}
else
if(a>=c || b>=c)
{
Node last=solve(a%c,b%c,c,n);
f=(a/c*n*(n+1)/2+b/c*(n+1)+last.f);
g=(n*(n+1)*(2*n+1)/6*Pow2(a/c)+(n+1)*Pow2(b/c)+(a/c)*(b/c)*n*(n+1)+2*(b/c)*last.f+2*(a/c)*last.h+last.g);
h=((a/c)*n*(n+1)*(2*n+1)/6+(b/c)*n*(n+1)/2+last.h);
}
else
{
int m=(a*n+b)/c;
Node last=solve(c,c-b-1,a,m-1);
f=(n*m-last.f);
g=(n*m*(m+1)-f-2*(last.h+last.f));
h=(n*m*(n+1)-last.g-last.f)/2;
}
return (Node){f,g,h};
}
}
int solve()
{
read(n,m,a,b1,b2);
n--; if(b1<b2) swap(b1,b2);
Node P1=Euclid::solve(a,b1,m,n);
Node P2=Euclid::solve(a,b2,m,n);
int ans1=a*a*n*(n+1)*(2*n+1)/6;
int ans2=a*(b1+b2)*n*(n+1)/2;
int ans3=(n+1)*b1*b2;
int ans4=m*(a*(P1.h+P2.h)+b1*P2.f+b2*P1.f);
int ans5=m*m*(P1.g+P2.g-P1.f+P2.f)/2;
return ans1+ans2+ans3-ans4+ans5;
}
bool Ending;
signed main()
{
int T=read(); while(T--) write(solve(),'\n');
cerr<<"\nused:"<<(abs(&Ending-&Beginning)/1048576)<<"MB\n";
return 0;
}
```