CF1798C题解

ncwzdlsd · 2023-10-23 15:38:15 · 题解

考虑一个区间 [l,r] 是可以满足的，当且仅当该区间的公共价签 c 满足条件 c=b_i d_i,i\in [l,r]，可得 \text{lcm}_{i\in[l,r]}b_i|c。

再考虑对于 d 的限制，要求 d_i|a_i，即 \dfrac{c}{b_i}|a_i，于是有 c|a_i b_i。那么显然有 c|\gcd_{i\in [l,r]}(a_i,b_i)。

于是得到最终的限制条件：

要求公共价签数最小，最大化每一段满足条件的区间的长即可。

代码如下：

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int maxn=2e5+5;
int a[maxn],b[maxn];

inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*f;
}

int lcm(int x,int y){return x*y/__gcd(x,y);}

void solve()
{
    int n=read();
    int ans=1;
    for(int i=1;i<=n;i++) a[i]=read(),b[i]=read();
    int t1=a[1]*b[1],t2=b[1];
    for(int i=2;i<=n;i++)
    {
        t1=__gcd(t1,(int)a[i]*b[i]),t2=lcm(t2,b[i]);
        if(t1%t2) t1=a[i]*b[i],t2=b[i],ans++;
    }
    cout<<ans<<endl;
}

signed main()
{
    int t=read();
    while(t--) solve();
    return 0;
}