[CF1798C] Candy Store 题解

aeiouaoeiu · 2025-11-12 19:08:13 · 题解

因为整个序列都要被划分，且显然这个区间长度具有单调性，于是考虑一段区间 [l,r] 能做到 c 相同的条件。

显然，\forall l\le i\le r,c\mid b_i，于是 c\mid \operatorname{lcm} b_i，取最少的限制，即 c=\operatorname{lcm} b_i，于是有 \operatorname{lcm} b_i\mid a_ib_i，进一步得到 \operatorname{lcm} b_i\mid \gcd a_ib_i。

如果觉得太跳跃了，可以从质因子角度出发，对于一个质数 p 若 a_i 拆出来 p^{\alpha_{p,i}}，b_i 拆出来 p^{\beta_{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}，对于每个 p 都拆出来 \min_i \alpha_{p,i}+\beta_{p,i} 的显然是 \gcd a_ib_i。

然后直接维护 \gcd a_i,b_i 和 \operatorname{lcm} b_i 就可以了，时间复杂度 \mathcal{O}(n\log V)。

::::info[code]

#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;
}

::::