CF710D Two Arithmetic Progressions

根號分治薄紗數論

看日報學習的根號分治：暴力美學——淺談根號分治 - paulzrm 的博客。

開始想學ODT的映射思想的推廣 - 金珂拉 的博客，結果先學了 ODT，又學了根號分治，才搞懂前置知識。

1. 什么是根號分治

   根號分治，是暴力美學的集大成體現。與其說是一種算法，我們不如稱它為一個常用的 trick。

   其實就是將兩個極端的暴力算法融合，根據不同數據選擇更優的暴力，即可保證復雜度始終在可接受范圍內。

2. 如何使用根號分治

   即寫出兩個不同暴力算法（通常是在小范圍內很快的和在大范圍內很快的），之后確定一個閾值，在不同范圍選擇不同暴力。

大概根號分治就是這樣，具體請看暴力美學——淺談根號分治 - paulzrm 的博客。

在這道題中，我們需要思考兩種方法（定 $t$ 為閾值，默認 $a_1\ge a_2$，默認 $l=\max(l,\max(b_1,b_2))$）：

1. $a_1\le t$，則 $a_2\le t$。以 $\text{lcm}(a_1,a_2)$ 為一個循環節，顯然的，一個循環節內至多有一個數同時出現在兩個數列中。因此暴力枚舉 $[\ l,\min(l+\text{lcm},r)\ ]$ 中的每一個數，若有 $i$ 使得 $i\in \text{數列1}\ \text{and}\ i \in \text{數列2}$，則可知共有 $\frac{(r-i)}{\text{lcm}+1}$ 個滿足條件的值；反之沒有所求值，輸出 0。

2. $a_1\gt t$。則可以暴力枚舉 $\text{數列1}$ 中的每一個處于 $[\ l,r\ ]$ 的數，若它同時處于 $\text{數列2}$ 則 ans++。

之后，我們進行復雜度分析：

1. 對于暴力1：時間復雜度為 $O(\text{lcm}(a_1,a_2))$。
2. 對于暴力2：時間復雜度為 $O(\frac{r-l+1}{a_1})$。

以下內容不保證正確性（數學太差了哭）：

故期望復雜度 $O(\text{lcm}(a_1,a_2)+(\frac{r-l+1}{a_1}))$，即 $O((t\times a_2)+(\frac{2e9}{t}))$，對于 $a_2$ 有限制 $a_2\le t$，使 $a_2=t$，則可算出閾值 $t=\sqrt[3]{2e9}$。約 $1259$。

對于閾值的計算并不準確，如果有更優方法歡迎指正。

代碼：

//pre
const int t=1259;
signed main() {
	LL ans=0;
	LL a1,b1,a2,b2,l,r;
	read(a1,b1,a2,b2,l,r);
	if(b1>l) l=b1;
	if(b2>l) l=b2;	//保證l的大小為 b_1,b_2,l 中的最大值
	if(a2>a1) swap(a1,a2),swap(b1,b2); //保證 a_1>a_2
	LL lcm=a2*a1/__gcd(a1,a2);	//計算lcm  (lcm(a,b)*gcd(a,b)=a*b)
	if(a1<t) { 	//a_1 小于閾值
		for(int i=l;i<=min(l+lcm,r);i++) {
			if((i-b1)%a1==(i-b2)%a2&&(i-b2)%a2==0) {	//若滿足題意
				ans=(r-i)/lcm+1;	//剩下有幾個循環節并加上當前位置的一個
				break;
			}
		}
	}
	else {
		LL x;
		if(b1>=l) x=b1;
		else x=b1+ceil(1.00*(l-b1)/a1)*a1;//確定從哪里開始枚舉（起始點要屬于數列1）
		for(;x<=r;x+=a1) if((x-b2)%a2==0&&(x-b2)/a2>=0) ++ans;	//滿足題意則ans++
	}
	write(ans); //輸出
	return 0;	//好習慣捏
}

pre 前的內容為頭文件與快讀快寫，如果需要戳這里。