专栏文章

[CF1798C] Candy Store 题解

aaeiouaoeiu
CF1798C题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min9gce9
此快照首次捕获于
2025/12/01 22:44
3 个月前
此快照最后确认于
2025/12/01 22:44
3 个月前
查看原文
因为整个序列都要被划分，且显然这个区间长度具有单调性，于是考虑一段区间 [l,r][l,r] 能做到 cc 相同的条件。
显然，∀l≤i≤r,c∣bi\forall l\le i\le r,c\mid b_i，于是 c∣lcm⁡bic\mid \operatorname{lcm} b_i，取最少的限制，即 c=lcm⁡bic=\operatorname{lcm} b_i，于是有 lcm⁡bi∣aibi\operatorname{lcm} b_i\mid a_ib_i，进一步得到 lcm⁡bi∣gcd⁡aibi\operatorname{lcm} b_i\mid \gcd a_ib_i。
如果觉得太跳跃了，可以从质因子角度出发，对于一个质数 pp 若 aia_i 拆出来 pαp,ip^{\alpha_{p,i}}，bib_i 拆出来 pβp,ip^{\beta_{p,i}}，则 lcm⁡bi∣aibi  ⟺  ∀p∈P,max⁡iβp,i≤min⁡iαp,i+βp,i\operatorname{lcm} b_i\mid a_ib_i\iff\forall p\in \mathbb P,\max_i \beta_{p,i}\le \min_i \alpha_{p,i}+\beta_{p,i}，对于每个 pp 都拆出来 min⁡iαp,i+βp,i\min_i \alpha_{p,i}+\beta_{p,i} 的显然是 gcd⁡aibi\gcd a_ib_i。
然后直接维护 gcd⁡ai,bi\gcd a_i,b_i 和 lcm⁡bi\operatorname{lcm} b_i 就可以了，时间复杂度 O(nlog⁡V)\mathcal{O}(n\log V)。
codeCPP
#include<bits/stdc++.h>
#define pb emplace_back
#define mp make_pair
using namespace std;
typedef unsigned long long ll;
typedef __int128 LL;
const ll maxn=200007,ee=1e18;
ll n,a[maxn],b[maxn],g,l,ans;
int main(void){
	//freopen("data.in","r",stdin);
	//freopen("data.out","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0);
	ll T=1; cin>>T;
	for(;T--;){
		cin>>n,ans=1,g=0,l=1;
		for(ll i=1;i<=n;i++) cin>>a[i]>>b[i];
		for(ll i=1;i<=n;i++){
			g=__gcd(g,a[i]*b[i]),l=l*b[i]/__gcd(l,b[i]);
			if(g%l) ans++,g=a[i]*b[i],l=b[i];
		}
		cout<<ans<<"\n";
	}
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...