洛谷链接

题解

之前没做过多少数论题，看到这道题一开始还以为是DP，根本没往数论上想，正好借此机会补充一下相关知识

整除的性质（转自OI-wiki）

  • $a\mid b\iff-a\mid b\iff a\mid-b\iff|a|\mid|b|$
  • $a\mid b\land b\mid c\implies a\mid c$
  • $a\mid b\land a\mid c\iff\forall x,y\in\mathbf{Z}, a\mid(xb+yc)$
  • $a\mid b\land b\mid a\implies b=\pm a$
  • 设 $m\ne0$，那么 $a\mid b\iff ma\mid mb$。
  • 设 $b\ne0$，那么 $a\mid b\implies|a|\le|b|$。
  • 设 $a\ne0,b=qa+c$，那么 $a\mid b\iff a\mid c$。

注意到对于符合题目要求的区间 $[l,r]$，都有 $d_{l}b_{l}=d_{l+1}b_{l+1}=…=d_{r}b_{r}=c_{l}=c_{l+1}=…=c_{r}$。

进而有 $lcm(b_{l},b_{l+1},…,b_{r}) \mid c_{l,l+1,…,r}$，这是区间能够符合题目要求的充要条件。

但 $c_{l,l+1,…,r}$ 的选择是个问题，这里可以通过题目中的其他性质绕开它本身。

题目中给出$d_{i} \mid a_{i}$，而 $d_{i}=\frac{c_{i}}{b_{i}}$，可以得出 $c_{i} \mid a_{i}b_{i}$，对于符合题目要求的区间，显然 $c_{l,l+1,…,r} \mid gcd(a_{l}b_{l},a_{l+1}b_{l+1},…,a_{r}b_{r})$（因为 $c_{l,l+1,…,r}$ 能整除 $gcd(a_{l}b_{l},a_{l+1}b_{l+1},…,a_{r}b_{r})$，所以也一定能整除它们的最大公约数），那么判断区间符合要求的条件就可以合并为 $lcm(b_{l},b_{l+1},…,b_{r}) \mid gcd(a_{l}b_{l},a_{l+1}b_{l+1},…,a_{r}b_{r})$，进而实现了与 $c$ 本身无关，能够满足该条件则必定能找到合适的 $c_{l,l+1,…,r}$。

可以顺序遍历 $a_{i}$ 和 $b_{i}$，在此过程中尽可能延长当前的合法区间，在此决策过程中改变之前已经对部分问题做出的最优决策不会使结果变得更好，因此可以贪心求得正确解。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<iostream>
#include<algorithm>
#include<cstring>
#define fastIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long LL;
// https://www.luogu.com.cn/problem/CF1798C

LL gcd(LL a,LL b){
    return b?gcd(b,a%b):a;
}

LL lcm(LL a, LL b){
    return a/gcd(a,b)*b;
}

int main(){
    fastIO
    int t,n;
    LL a,b;
    cin>>t;
    while(t--){
        cin>>n;
        int ans=1;
        LL x=0,y=1;
        for(int i=1;i<=n;i++){
            cin>>a>>b;
            x=gcd(x,a*b),y=lcm(y,b);
            if(x%y){
                ans++;
                x=a*b;
                y=b;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}