cf-div2-860c

题目链接：https://codeforces.com/contest/1798/problem/C

大致题意：给你一个长度为\(n(n<=2e5)\)的序列的\(a_i,b_i\)，让你把这个序列分成数目最少的段，每一段都有一个值\(c\)，\(c=a_i的一个约数乘以b_i\)。

比赛没写出的题。

思路：\(首先一段里面的所有a_i*b_i能够整除c，易得c是所有b的最小公倍数(这个是满足条件的最小值，条件最不苛刻。)，则这一段所有a*b的最大公约数能够整除lcm(b_i)即可。\)

一个小结论的证明：
反证法：不如就设两个数\(x,y\)，\(g = gcd(x,y)\)，\(z\)同时可以被这两个数整除，但\(g\)不能整除\(z\)，
则\(lcm(g,z)\)一定大于\(g\)，但这个数也可以同时被\(x,y\)整除，所以\(g\)不可能为\(x,y\)的最大公约数。得证。

结论：如果某一段数都同时可以整除以某一个数，则这一段的最大公约数也一定可以整除以这一个数。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
int A[N],B[N];
long long gcd(long long x,long long y){
	if (!y) return x;
	else return gcd(y,x%y);
}
long long lcm(long long x,long long y){
	return x*y/gcd(x,y);
}
void solve(){
	int n;
	cin>>n;
	for (int i=1;i<=n;i++) cin>>A[i]>>B[i];
	int ans = 1;
	long long g = 0,l = 1;
	for (int i=1;i<=n;i++){
		if (gcd(g,1ll*A[i]*B[i])%lcm(l,B[i])!=0){
			g = A[i]*1ll*B[i],l = B[i];
			ans++;
		}
		else{
			g = gcd(g,1ll*A[i]*B[i]);
			l = lcm(l,B[i]);
		}
	}
	cout<<ans<<'\n';
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int T;
	T = 1;
	cin>>T;
	while(T--) solve();
	return 0;
}