题解：P14781 [COCI 2025/2026 #3] 尺子 / Ravnalo

解题思路（题目传送门）

一定需要画的 $n+2$ 条边（左右边界和底部），加上横线总数（仅包括柱子的顶部和柱子的 $b_i-1$ 条 $b_i$ 等分线），再减去可以合并成一条线的线段个数。

计算公式

$cnt=n+2+\sum\limits_{i=1}^nb_i-\sum\limits_{i=1}^{n-1}k_i$

PS：$k_i$ 表示第 $i$ 根柱子和第 $i+1$ 根柱子的等分线中可以合并成一条线的线段个数。

$k_i=\gcd(a_i \times b_{i+1},a_{i+1} \times b_i)/\max(a_i,a_{i+1})$

时间复杂度

枚举每个位置的时间复杂度是 $O(n)$，计算最大公因数的时间复杂度是 $O(\log k)$，所以程序的总时间复杂度是 $O(n \log k)$。

AC 代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+10;
int n,a[N],b[N],cnt;
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
    cin>>n;
    cnt+=n+2;//记录画出所有柱子的外边界所需的笔画数。
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i],cnt+=b[i];
    for(int i=1;i<n;i++){
        int x=a[i]*b[i+1],y=a[i+1]*b[i];
        cnt-=__gcd(x,y)/max(a[i],a[i+1]);//__gcd(x,y)是万能头自带的求最大公因数的函数。
    }
    cout<<cnt;
	return 0;
}