快速讀寫和__int128

這塊算是補充知識點，但僅作為高精度算法的臨時替代，在有的題若使用__int128也會溢出，則只能用高精度算法。

雖然在 99% 的題目中，scanf 以及 printf 來處理輸入和輸出已經足夠快了。但是，如果輸入和輸出的規模特別龐大，或者出題人卡常，scanf 和 printf 也是會超時的，這個時候就需要更加快速的讀寫方式。

同樣的，雖然在 99% 的題目中，long long 已經足夠我們應付較大的整數。但是，如果題目中數的范圍過大，相乘也是有可能超過 long long 的最大范圍。如果只是大一點點，此時可以用 __int128 來存儲。

快速讀寫

快速讀寫有很多種版本，接下來要介紹一種容易實現且夠用的版本 - getchar/putchar 結合秦九韶算法。

前置知識：

1. 在計算機的視角，所有的整數其實是一個一個的字符串，每個數拆開看就是一個一個字符。因此，對于一個整數，可以當成字符串，一個一個字符的輸入進來。同理，輸出一個整數的時候，也可以當成字符串，一個一個字符的輸出。

2. getchar/putchar 這種輸入輸出方式相較于 scanf/printf 而言，速度更快。

于是，就可以利用 getchar 將字符轉換成整數輸入，利用 putchar 將整數轉換成字符輸出。

如果這種方式還是超時，那就把 getchar 換成 getchar_unlocked。如果換完之后還是超時，那就是毒瘤題，可以忽視，或者就是算法本身的時間復雜度有問題。

但是，getchar_unlocked 只能在 Linux 系統下使用，因此要慎用。

這里通過模板題進行檢測：

P10815 【模板】快速讀入 - 洛谷

#include<bits/stdc++.h>
using namespace std;inline int read(){int flag=1,ans=0;//這個函數只有在linux操作系統下的gcc系列編譯器才能使用 //當然，洛谷也能使用，不然最后一個樣例無法通過 char ch=getchar_unlocked();//一般編譯器用這個 
//	char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')flag=-1;ch=getchar_unlocked();
//		ch=getchar();}while(ch>='0'&&ch<='9'){ans=ans*10+ch-'0';ch=getchar_unlocked();
//		ch=getchar();}return ans*flag; 
}inline void print(int a){if(a<0){putchar('-');a=-a;}if(a>9)print(a/10);putchar(a%10+'0');
}int main() {int n=read();int sum=0,x;while(n--){x=read();sum+=x;}print(sum);return 0;
}

__int128

【更大的整數__int128】

__int128 就是占用 128 字節的整數存儲類型，范圍就是 $?2^{127}～2^{127}?1$。
即
$$\begin{gathered} ?170141183460469231731687303715884105728 \\ ～170141183460469231731687303715884105727 \end{gathered}$$。

170 1411 8346 0469 2317 3168 7303 7158 8410 5727//39位

• 對比int的范圍$?2^{32}～2^{32}?1$，即$?2147483648～2147483647$。

  無符號情況下$0～4294967295$。

• long long：$?2^{64}～2^{64}?1$，即$?9223372036854775808～9223372036854775807$。

  無符號情況下$0～18446744073709551615$。

• 如果使用了 unsigned __int128，則范圍變成 $0～2^{128}$，即約 39 位數。
  $0～340282366920938463463374607431768211455$。

當數據范圍超過 long long，但是還不足以用上高精度算法的時候，用 __int128 是個不錯的選擇。

但是，__int128 是不能直接用 cin、cout、scanf 以及 printf 輸入或者輸出的。只能按照字符的方式輸入輸出，也就是我們剛剛學習的快速讀寫的方式。不過，當讀入進來之后，用法和普通的整型變量一致。

__int128的使用示例（需要在gcc系IDE使用，例如Devc++）：

#include<bits/stdc++.h>
using namespace std;
typedef unsigned __int128 uint;
typedef __int128 _int;inline void print(uint n){if(n>9)print(n/10);putchar(n%10+'0');
}inline void print(_int n){if(n<0){putchar('-');n=-n;}if(n>9)print(n/10);putchar(n%10+'0');
}inline _int read(){_int flag=1,ans=0;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')flag=-1;ch=getchar();}while(ch>='0'&&ch<='9'){ans=ans*10+ch-'0';ch=getchar();}return ans*flag; 
}void f1(){_int mmax=(_int(1)<<127)-1;print(mmax);cout<<endl;_int mmin=(_int(1)<<127);print(mmin+1);//無法直接輸出-2^128 cout<<endl;
}void f2(){uint mmax=~uint(0);print(mmax);cout<<endl;
}void f3(){_int a=114514;print(a);cout<<endl;a=read();print(a);cout<<endl;a+=3;print(a);cout<<endl;a-=486;print(a);cout<<endl;a*=1435;print(a);cout<<endl;a/=1435;print(a);cout<<endl;a%=10007;print(a);cout<<endl;
}int main() {
//	f1();
//	f2();f3();return 0;
}

__int128 再好用，缺陷也很多：

1. 不通用。 __int128 并沒有在任何一個 c++ 標準中嚴格定義，所以目前它只是 GCC 系列編譯器的專屬。目前測試，只在 Linux 系統下能夠正常使用，在其他編譯器例如MSVC不能使用。因此如果要使用，就要看比賽中的編譯器，是否是 Linux。

2. 不方便。 __int128 目前是不支持直接讀入、輸出的。也就是無法用 cin、cout、scanf 以及 printf 輸入或者輸出這種類型的數。只能按照字符的方式輸入輸出，也就是我們剛剛學習的快速讀寫的方式。

3. 空間大，速度慢。 __int128 占用了 16 個字節來存，空間超限的風險顯著增加。

但是，在有些題目中，__int128 還是足夠我們使用的。

中國剩余定理和線性同余方程組

引入線性同余方程組：南北朝時期《孫子算經》中有個問題：有物不知其數，三三數之剩二，五五數之剩三，七七數之剩二。問物幾何？

用數學公式翻譯過來就是一個線性同余方程組：

$$?\begin{array}{l}x\equiv 2(\text{mod?}3)\\ x\equiv 3(\text{mod?}5)\\ x\equiv 2(\text{mod?}7)\end{array}$$

線性同余方程組：求這個方程組的最小非負整數解。

$$?\begin{array}{l}x\equiv r_1(\text{mod?}{m}_1)\\ x\equiv r_2(\text{mod?}{m}_2)\\ ?\\ x\equiv r_n(\text{mod?}{m}_n)\end{array}$$

中國剩余定理(CRT)

前提：所有的模數 $m_1,m_2,...,m_n$ 兩兩互質。因此中國剩余定理的使用比較局限。

原理：中國剩余定理是基于“構造法”得出的結果。以下給出 $n=3$ 的構造過程，$n$ 等于任意數的構造過程是一樣的。

對于這個方程組：
$?\begin{array}{l}x\equiv r_1(\text{mod?}{m}_1)\\ x\equiv r_2(\text{mod?}{m}_2)\\ x\equiv r_3(\text{mod?}{m}_3)\end{array}$

或

$?\begin{array}{l}x\mathrm{mod}{m}_1=r_1\\ x\mathrm{mod}{m}_2=r_2\\ x\mathrm{mod}{m}_3=r_3\end{array}$

記 $M=m_1\times m_2\times m_3$，構造解：$x=C_1+C_2+C_3$，其中：

• $C_1\text{?mod?}{m}_1=r_1,C_1\text{?mod?}{m}_2=0,C_1\text{?mod?}{m}_3=0$

• $C_2\text{?mod?}{m}_1=0,C_2\text{?mod?}{m}_2=r_2,C_2\text{?mod?}{m}_3=0$

• $C_3\text{?mod?}{m}_1=0,C_3\text{?mod?}{m}_2=0,C_3\text{?mod?}{m}_3=r_3$

這樣$x\mathrm{mod}m1=C_1\mathrm{mod}m1+C_2\mathrm{mod}m1+C_3\mathrm{mod}{m}_1=r_1$，其他$m2$、$m3$同理。

因此只要能構造出這樣的 $x$，那么 $x$ 就是我們要的解。

$C_1$、$C_2$和$C_3$的構造方式：

• $C_1=r_1\times m_2\times m_3\times (m_2\times m_3{)}^{?1},$

  $(m_2 \times m_3)^{-1} $為模$m_1$意義下的逆元，$m_2 \times m_3 \times (m_2 \times m_3)^{-1}\bmod m_1$最后的結果是1。所以$C_1\bmod m_1=r_1$，$C_1\bmod m_2=C_1\bmod m_3=0$。

• $C_2=r_2\times m_1\times m_3\times (m_1\times m_3{)}^{?1},$ 其中 $(m_1 \times m_3)^{-1} $為模$m_1$意義下的逆元。

• $C_3=r_3\times m_1\times m_2\times (m_1\times m_2{)}^{?1},$ 其中 $(m_1 \times m_2)^{-1} $為模$m_1$意義下的逆元。

當$x$加減$M$的若干倍時，依舊是滿足方程，因此最小非負整數解就是
$(x\text{?mod?}M+M)\text{?mod?}M$。

整個方程的通解是$x+kM$。

以《孫子算經》中的問題為例：
$?\begin{array}{l}x\equiv 2(\text{mod?}3)\\ x\equiv 3(\text{mod?}5)\\ x\equiv 2(\text{mod?}7)\end{array}$

1. 計算每一個方程的 $C_i$：
   $C_1=r_1\times m_2\times m_3\times (m_2\times m_3{)}^{?1}=2\times 5\times 7\times 35^{?1}(\text{mod?}3)=2\times 5\times 7\times 2=140$
   $C_2=r_2\times m_1\times m_3\times (m_1\times m_3{)}^{?1}=3\times 3\times 7\times 21^{?1}(\text{mod?}5)=3\times 3\times 7\times 1=63$
   $C_3=r_3\times m_1\times m_2\times (m_1\times m_2{)}^{?1}=2\times 3\times 5\times 15^{?1}(\text{mod?}7)=2\times 3\times 5\times 1=30$

2. 計算結果：$x=(140+63+30)\text{?mod?}105=233\text{?mod?}105=23$

推廣：$n$取任意數的時候，構造方式也是同理。

• $C_1=r_1\times m_2\times m_3\times \dots \times m_n\times (m_2\times m_3\times \dots \times m_n{)}^{?1}$,
• $C_2=r_2\times m_1\times m_3\times \dots \times m_n\times (m_1\times m_3\times \dots \times m_n{)}^{?1}$,
• $\dots$
• $C_n=r_n\times m_1\times m_2\times \dots \times m_{n?1}\times (m_1\times m_2\times \dots \times m_{n?1}{)}^{?1}$。

當 $m_1,m_2,\dots ,m_n$ 兩兩互質時，一定存在這樣的 $C_1,C_2,\dots ,C_n$，因為對應的逆元是一定存在的。且通解為：$X=k\times \text{lcm}+x$，其中$\text{lcm}$因為$m_i$全是質數，所以實際相當于整體的乘積。

總結：在算法競賽中，中國剩余定理應用的算法流程：

1. 計算所有模數的乘積 $M=m_1\times m_2\times \dots \times m_n$；

2. 計算第 $i$ 個方程的 $c_i=\frac{M}{m_i}$；

3. 計算 $c_i$ 在模 $m_i$ 意義下的逆元 $c_i^{?1}$（擴歐算法）；

4. 最終解為 $x={\sum }_{i=1}^n{r}_i{c}_i{c}_i^{?1}(\text{mod?}M)$。

中國剩余定理OJ示例

模板題曹沖養豬 - 洛谷

P1495 【模板】中國剩余定理（CRT）/ 曹沖養豬 - 洛谷

1634：【例 4】曹沖養豬

CRT的模板題，因為數據量大，需要使用快速冪改裝的龜速乘算法來進行最后的求乘。

龜速乘是能一步出結果的乘法，拆分成若干步乘完，這樣做能最大程度保證不溢出，但犧牲了速度。

#include<bits/stdc++.h>
using namespace std;typedef long long LL;//擴展歐幾里得算法
void exgcd(LL a, LL b, LL& x, LL& y) {if (!b) {x = 1; y = 0;return;}LL x1, y1;exgcd(b, a % b, x1, y1);x = y1; y = x1 - a / b * y1;
}//龜速乘，防溢出
LL qmul(LL a, LL b, LL m) {LL ans = 0;while (b) {if (b % 2)ans = (ans%m + a%m) % m;a = (a + a) % m;b /= 2;}return ans;
}void ac() {LL n;cin >> n;vector<LL>r(n + 1, 0), m(n + 1, 1);for (LL i = 1; i <= n; i++)cin >> m[i] >> r[i];//中國剩余定理LL M = 1;for (auto& x : m)M *= x;LL ans = 0;for (LL i = 1; i <= n; i++) {LL ci = M / m[i];LL x, y;exgcd(ci, m[i], x, y);x = (x % m[i] + m[i]) % m[i];//快速冪改裝的鬼速乘算法ans = (ans % M + qmul(qmul(r[i], ci, M), x, M)) % M;}cout << ans << endl;
}int main() {ios::sync_with_stdio(false);cin.tie(0);int T = 1;//cin >> T;while (T--)ac();return 0;
}

模板題猜數字 - 洛谷

[P3868 TJOI2009] 猜數字 - 洛谷

中國剩余定理的推廣模板。題目要求的是$b_i\mid (n?a_i)$，即$(n?a_i)\mathrm{mod}{b}_i=0$，將等式拆分開就是$n\mathrm{mod}{b}_i?a_i\mathrm{mod}{b}_i=0$，即$n\equiv a_i(\mathrm{mod}{b}_i)$。

因此題目要求的就是同余方程組$n\equiv a_i(\mathrm{mod}{b}_i)$的解，$n$是未知數。

#include<bits/stdc++.h>
using namespace std;typedef long long LL;void exgcd(LL a, LL b, LL& x, LL& y) {if (!b) {x = 1; y = 0;return;}LL x1, y1;exgcd(b, a % b, x1, y1);x = y1; y = x1 - a / b * y1;
}LL qmul(LL a, LL b, LL m) {LL ans = 0;while (b) {if (b % 2)ans = (ans + a) % m;a = (a * 2) % m;b /= 2;}return ans;
}void ac() {int n;cin >> n;vector<LL>a(n + 1, 1), b(a);for (int i = 1; i <= n; i++)cin >> a[i];LL M = 1;for (int i = 1; i <= n; i++)cin >> b[i], M *= b[i];//CRT推廣LL ans = 0;for (int i = 1; i <= n; i++) {LL ci = M / b[i];LL x, y;exgcd(ci, b[i], x, y);x = (x % b[i] + b[i]) % b[i];//a[i]為負數，需要放第1個形參，否則會死循環ans = (ans + qmul(qmul(a[i], ci, M), x, M) + M) % M;}cout << ans << endl;
}int main() {ios::sync_with_stdio(false);cin.tie(0);int T = 1;//cin >> T;while (T--)ac();return 0;
}

擴展中國剩余定理

中國剩余定理只能處理所有模數兩兩互質的情況，如果模數不互質，CRT就不適用了。

【擴展中國剩余定理 - EXCRT】

同樣是求線性同余方程組：

$?\begin{array}{l}x\equiv r_1(\text{mod?}{m}_1)\\ x\equiv r_2(\text{mod?}{m}_2)\\ ?\\ x\equiv r_n(\text{mod?}{m}_n)\end{array}$

思路是將任意整數 $X$ 不斷迭代成最終解。

這里補充一個方程：$x\equiv r_0(\text{mod?}{m}_0)$，其中 $r_0=0,m_0=1$。

設最終的通解為：$ret=x\times m_0+r_0$，初始時 $m_0=1,r_0=0$。

然后依次迭代后面的方程，使的最終解 $ret$ 依次滿足后續的方程。

設當前取的方程為：$x\equiv r_i(\text{mod?}{m}_i)$，即 $ret=y\times m_i+r_i$

1. 根據兩式右邊相等：$ret=x\times m_0+r_0=y\times m_i+r_i$,

2. 于是：$x\times m_0?y\times m_i=r_i?r_0$,

3. 形如 $ax+by=c$，其中 $a=m_0,b=m_i,c=r_i?r_0$

4. 根據擴歐算法，可以解出特解 $x_0,y_0$。（如果無解，算法結束）

5. 通解為 $x=x_0+\frac{b}{d}\times k$，代入最終解中：$ret=(x_0+\frac{b}{d}\times k)\times m_0+r_0$

6. 整理得：$ret=k(\frac{b}{d}\times m_0)+(x_0\times m_0+r_0)$，既滿足之前的方程，也滿足當前方程。

其中新的 $m^{\prime }=\frac{b}{d}\times m_0,r^{\prime }=x_0\times m_0+r$

7. 利用$ret$的表達式繼續迭代下一個方程。直到迭代完所有的方程或某個方程無解為止。

例如：

$?\begin{array}{l}x\equiv 2(\text{mod?}3)\\ x\equiv 3(\text{mod?}5)\\ x\equiv 2(\text{mod?}7)\end{array}$

補上一個方程 $x\equiv 0(\text{mod?}1)$，最終解 $ret=x\times 1+0$

迭代第一個方程：$ret=y\times 3+2$

• $ret=x\times 1+0=y\times 3+2$，即 $x?3y=2$，也可看做 $x+3y=2$。

• 利用擴歐算法得

$\{\begin{array}{l}x=2+3k\\ y=0?k\end{array}$

• 此時 $ret=k\times 3+2$ 滿足第一個方程。$k$是整數，在后續迭代中也可看成新的未知數。

迭代第二個方程：$ret=y\times 5+3$

• $ret=x\times 3+2=y\times 5+3$，即 $3x+5y=1$

• 利用擴歐算法解得：
  $\{\begin{array}{l}x=2+5\times k\\ y=?1?3\times k\end{array}$

• 于是將$x$的通解代入 $ret$ 中得：$ret=k\times 15+8$。此時 $ret$ 滿足前兩個方程。

迭代第三個方程：$ret=y\times 7+2$

• $ret=x\times 15+8=y\times 7+2$，即 $15x+7y=?6$

• 利用擴歐算法解得：
  $\{\begin{array}{l}x=?6+7\times k\\ y=12?15\times k\end{array}$

• 代入 $ret$ 中得：$ret=k\times 105?82=k\times 105+23$。

此時 $ret$ 滿足所有方程，并且 $23$ 為最小非負整數解。

擴展中國剩余定理OJ示例

之前的OJ例如P1495 【模板】中國剩余定理（CRT）/ 曹沖養豬 - 洛谷、[P3868 TJOI2009] 猜數字 - 洛谷也能用擴展中國剩余定理解決。

模板題擴展中國剩余定理（EXCRT） - 洛谷

P4777 【模板】擴展中國剩余定理（EXCRT） - 洛谷

需要注意的點是，構造的方程$ax+by=c$中$c$需要為最小整數，以及利用$ax+by=\text{gcd}(a,b)$求方程$ax+by=c$的特解時，需要使用龜速乘算法，這些都是為防止溢出需要做的操作。

#include<bits/stdc++.h>
using namespace std;typedef long long LL;LL exgcd(LL a, LL b, LL& x, LL& y) {if (!b) {x = 1; y = 0;return a;}LL x1, y1, d = exgcd(b, a % b, x1, y1);x = y1; y = x1 - a / b * y1;return d;
}LL qmul(LL a, LL b, LL m) {LL ans = 0;while (b) {if (b & 1)ans = (ans + a) % m;a = (a * 2) % m;b >>= 1;}return ans;
}void ac() {int n;cin >> n;vector<LL>a(n + 1, 0), b(a);for (int i = 1; i <= n; i++)cin >> a[i] >> b[i];//擴展中國剩余定理//ret = k*m+rLL m = 1, r = 0;for (int i = 1; i <= n; i++) {//解不定方程mx+a[i]y=b[i]-rLL x, y, d = exgcd(m, a[i], x, y), c = b[i] - r;c = (c % a[i] + a[i]) % a[i];if (c % d) {cout << -1 << endl;return;}y = a[i] / d;//y是不定方程的另一個解，不重要，于是代碼復用//加龜速乘，擦邊通關OJx = qmul(x, c / d, y);x = (x % y + y) % y;r = x * m + r;m = y * m;r = (r % m + m) % m;//ret = k*m+r，可以用m對r進行范圍限制}cout << r << endl;
}int main() {ios::sync_with_stdio(false);cin.tie(0);int T = 1;//cin >> T;while (T--)ac();return 0;
}

NOI2018 屠龍勇士

[P4774 NOI2018] 屠龍勇士 - 洛谷

這種個人感覺是真正的壓軸題或準壓軸題級別的題，題目又臭又長，還得逐句分析，其中分析還得分階段，嚴重的還有分類談論，每個階段的分析還得有聯系，不然無法流暢地翻譯成自然語言或代碼。

在實現時往往伴隨著知識點的嵌套使用，極其考驗綜合能力。

讀題：

首先是游戲規則：

1. 1條龍，打它會使Hp會變負數，然后回血，Hp恢復到0時龍死去，否則不能死去。

   例如龍的初始Hp為 5，將血量斬殺到 -4，龍的回血$p=2$，回 2 次后龍會死去；或剛好砍到Hp位0，則龍死去。

   但如果某幾次攻擊將血量斬殺到-3，龍回血2次后血量變成1，龍就還能蹦迪。

   所以選擇的武器需要將龍的血量控制在$p$的整數倍才能擊殺。

2. 砍龍需要選劍，砍死龍得新劍。

然后這人想寫個腳本之類的東西掛機刷游戲，腳本原理：

1. 選擇當前有的、傷害不大于龍Hp、同時傷害是最大的劍。沒有就選傷害最小的。

   例如Hp = 5，劍 a [ i ] = { 1 , 2 , 3 , 4 , 4 , 5 , 6 , 7 , 8 , 9 } a[i]=\{1,2,3,4,4,5,6,7,8,9\} a[i]={1,2,3,4,4,5,6,7,8,9}，此時選a[5]=5的劍。

   劍$a[i]=6,7$，此時選a[0]=6的劍。

2. 對每條龍，設置固定的攻擊次數$x$。

之后就是解題思路：

1. 確定哪條龍用哪把劍。

   既然要選劍，則劍應該有序，想到排序。

   對每條龍，考慮Hp和獎勵，在劍的集合中選不大于龍的血量且傷害最大的，首先應該想到二分優化的枚舉，二分的話要考慮數組，數組需要看數據量是否支持。

   因為有消耗和獎勵，需要頻繁插入和刪除還有取出指定位置的劍，想到集合multiset，插入和取出都是$O(\log n)$。可以選擇用upper_bound快速查找，但要注意這個成員函數找的是大于Hp的最小值，所以需要使返回的迭代器減1，邊界情況是所有劍都大于Hp。

2. 如何確定攻擊次數$x$。

   根據題意解讀的每條龍的信息{初始血量Hp,恢復rv,劍的傷害swd,打的次數x,恢復次數y}，根據游戲規則構造等式$Hp?swd\times x+rv\times y=0$，即$swd\times x=rv\times y+Hp$，看到這個等式想到
   $swd\times x÷rv=y\dots Hp$，2個等式$swd\times x=rv\times y+Hp$和$swd\times x÷rv=y\dots Hp$中，$y$也是未知數，所以根據這2個等式可得出同余方程 $swd\times x\equiv Hp(\mathrm{mod}rv)$。

   對所有龍的同余方程組：

   $?\begin{array}{l}sw{d}_{1}x\equiv H{p}_1(\mathrm{mod}r{v}_1)\\ sw{d}_{2}x\equiv H{p}_2(\mathrm{mod}r{v}_2)\\ \dots \\ sw{d}_{n}x\equiv H{p}_n(\mathrm{mod}r{v}_n)\end{array}$

   解出$x$的，即為攻擊次數。和之前的同余方程組不同，這個方程組的未知數帶系數，使用擴展中國剩余定理時需要注意細節。

   • 擴展中國剩余定理解同余方程組：

     約定攻擊次數$ret$，恢復力$m=rv$，$r=Hp$。

     設方程$ret=km+r$，$m=1$，$r=0$。

     對任一方程$swd\times x\equiv Hp(\mathrm{mod}rv)$，其實就是$swd\times ret=y\times rv+Hp$，次數$x$換成了$ret$，都表示攻擊次數。

     聯立：

     $\{\begin{array}{l}ret=km+r\\ swd\times ret=y\times rv+Hp\end{array}$

     第1個方程左右同時乘$swd$消去$ret$，并移項得

     $swd\times m\times k+y\times rv=Hp?swd\times r$，此時得到一個不定方程，

     對比$Ax+By=C$，$A=swd\times m$，$B=rv$，$C=Hp?swd\times r$。

     之后就是熟悉的流程：擴展歐幾里得算法求$k$（或者說$x$）的通解，代入$ret=km+r$得到新的$m$和$r$，并用它們繼續迭代其他方程。

     對比之前的擴展中國剩余定理，多個常數系數時只需要聯立方程組即可解決。

   • 細節問題：

     • 防溢出。

       在乘法階段用龜速乘算法代替。同時對方程$swd\times x\equiv Hp(\mathrm{mod}rv)$，$swd\times x$和$Hp$可以都同時先模$m$限制大小，即$(swd\times x\mathrm{mod}rv)\equiv (Hp\mathrm{mod}rv)(\mathrm{mod}rv)$。其他地方能取模盡量取模。

     • 最終結果$ret=km+r$中的$r$可能不是正確答案，而是只是方程組的解，此時還需要$y>0$也就是恢復次數也要大于0。

       此時對于每條龍的血量$Hp$和劍的傷害$swd$，在求攻擊次數時需為$?\frac{Hp}{swd}?$。例如Hp為5的龍，傷害為2的劍，攻擊次數需要為$?\frac{5}{2}?=3$，才能壓血線到負數。

       同時需要將每條龍斬到負數Hp的攻擊次數并不完全相同，此時需要取最大的次數，取方程中攻擊次數大于最大攻擊次數的特解，才能保證將所有的龍的血量砍到負數。這里假設所有龍中需要被砍的最多的次數為$\text{max\_tm}$，$\text{max\_tm}=?\frac{\text{Hp}}{\text{swd}}?$。

       對表示攻擊次數的方程$ret=km+r$，需有$ret\ge \text{max\_tm}$。

       • $r\ge \text{max\_tm}$，此時$ret=r$。

       • $r<\text{max\_tm}$，此時$ret=?\frac{\text{max\_tm}?r}{m}?\times m+r$。

         這里$?\frac{\text{max\_tm}?r}{m}?$表示需要在最小正整數解的基礎上增加的模數$m$的數量，這樣做是為了求能以最低的固定攻擊次數將所有的龍都壓到負數Hp的特解。

參考程序（變量名和數組名與分析對應）：

#include<bits/stdc++.h>
using namespace std;typedef long long LL;LL exgcd(LL a, LL b, LL& x, LL& y) {if (!b) {x = 1; y = 0;return a;}LL x1, y1, d = exgcd(b, a % b, x1, y1);x = y1; y = x1 - a / b * y1;return d;
}LL qmul(LL a, LL b, LL m) {LL ans = 0;while (b) {if (b % 2)ans = (ans + a) % m;a = (a * 2) % m;b /= 2;}return ans;
}void ac() {int N, M;cin >> N >> M;//Hp血量，rv恢復，rd reword獎勵,swd sword砍龍時用的劍vector<LL>Hp(N + 1, 0), rv(Hp), rd(Hp),swd(Hp);multiset<LL>st;LL max_tm = 0;//max times，最難砍的龍需要的次數for (int i = 1; i <= N; i++)cin >> Hp[i];for (int i = 1; i <= N; i++)cin >> rv[i];for (int i = 1; i <= N; i++)cin >> rd[i];for (int i = 1; i <= M; i++) {LL x; cin >> x;st.insert(x);}//選擇劍for (int i = 1; i <= N; i++) {//二分auto it = st.upper_bound(Hp[i]);if (it != st.begin())--it;swd[i] = *it;max_tm = max(max_tm, (Hp[i] + swd[i] - 1) / swd[i]);st.erase(it);st.insert(rd[i]);}//確定攻擊次數//擴展中國剩余定理，初始方程ret=mx+r，m是rv，r是hp，res是攻擊次數//對應同余方程（組）swd*x % rv = HpLL m = 1, r = 0;for (int i = 1; i <= N; i++) {//Hp-swd*x+rv*y=0 得到同余方程//聯立ret=mx+r和Hp-swd*x+rv*y=0//得到不定方程 (swd-m) x + rv* y= Hp-swd*rLL A = qmul(swd[i] ,m,rv[i]), B = rv[i], C = Hp[i] - swd[i] * r;C = (C % B + B) % B;LL x, y, d = exgcd(A, B, x, y);if (C % d) {cout << -1 << endl;return;}LL g1 = B / d;x = qmul(x,C / d,g1);x = (x % g1 + g1) % g1;r = r + x * m;m = g1 * m;r = (r % m + m) % m;}//最小正整數解可能無法將所有的龍都砍到負數Hp需要求特解if (r < max_tm)r = r + (max_tm - r + m - 1) / m * m;cout << r<<endl;
}int main() {ios::sync_with_stdio(false);cin.tie(0);int T = 1;cin >> T;while (T--)ac();return 0;
}