题解：P15053 [UOI 2023 II Stage] Land plots

· · 题解

题目传送门

题意：

一块正方形大地块被 (n-1) 条竖线和 (n−1) 条横线分成 n×n 个小矩形。行从下到上编号 1∼n，列从左到右编号 1∼n。

思路与代码

看到题觉得是数论，所以推式子。\ 定义第 i 列的宽度为 c_i，第 j 行的高度为 r_j，则则每个小矩形的面积为：s_{i,j}=c_i\times r_j。\ 结论：

S_{p,q}=a_p \prod_{i=p+1}^{q} \frac{a_i}{b_{i-1}} \quad (q\ge p) S_{p,q}=a_p \prod_{i=q+1}^{p} \frac{b_{i-1}}{a_i} \quad (q<p)
具体实现：

直接做分数连乘会 WA，所以用质因数分解 + 指数累加：

用一个 map<ll,int>e 记录每个质因数的指数。add(x, s) 函数将 x 分解质因数，每个质因数的指数加上 s（s=1 表示乘，s=-1 表示除）。\ 先 add(a[p], 1)，再根据 p,q 的大小关系遍历连乘 / 连除。\ 最后遍历 map，将每个质因数按其指数累乘得到答案。\ 计算过程可能爆 long long，可以使用 __int128 累乘，最终转回 long long 输出。

code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[1005],b[1005];
map<ll,int>e;
void add(ll x,int s)
{
    for(ll d=2;d*d<=x;d++)
    while(x%d==0)
    {
        e[d]+=s;
        x/=d;
    }
    if(x>1)e[x]+=s;
}
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n-1;i++)cin>>b[i];
    int p,q;
    cin>>p>>q;
    add(a[p],1);
    if(q>=p)
        for(int i=p;i<=q-1;i++)
        {
            add(b[k],-1);
            add(a[k+1],1);
        }
    else
        for(int i=q;i<=p-1;i++)
        {
            add(b[k],1);
            add(a[k+1],-1);
        }
    bool f=0;
    for(auto i:e) if(i.second!=0)f=1;
    if(!f)cout<<"1 1\n";
    else for(auto i:e) if(i.second!=0)cout<<i.first<<" "<<i.second<<"\n";
    return 0;
}