自动搬运

查看原文

来自洛谷，原作者为

	EMO_smile 用传说重塑我 用疼痛重铸我

搬运于2025-08-24 22:57:12，当前版本为作者最后更新于2024-07-30 13:57:03，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P10358 [PA2024] Obrazy

题目传送门

题意分析：

1.特判

我们很容易能够想到本题的特殊判断：即当最小的画框都不可能覆盖整个矩形墙面时，输出 $-1$。

2.常规

若我们将墙面的长设为 $l$，宽设为 $r$,画框最小边长为 $a[i]$，画框可覆盖面积为 $ans$（因为需要保证画框的完整性，不能让一个 $2\times2$ 的画框变为 $1\times4$），易得：

当 $ans < l\times r$ 时，输出 $-1$。

我们可用一个变量 $tmp$ 来表示当前画框可覆盖面积， $a1[i]$ 来判断第 $i$ 个画框的面积，判断当前有多少个 $a1[i-1]$ 面积的画框可以被 $a1[i]$ 整除即可：

tmp=(l-(l%a[i]))*(r-(r%a[i]));
ans-=tmp/a1[i-1];//较小画框可换数量
ans+=tmp/a1[i];//较大画框可换数量

代码：

//#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
using namespace std;
inline long long read(){//快读
	long long x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-'){
			f=-1;
		}
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=(x<<1)+(x<<3)+(c^'0');
		c=getchar();
	}
	return x*f;
}
void write(int x){//快写（虽然不经常用）
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9){
		write(x/10);
	}
	putchar(x%10+'0');
	return;
}
long long a[1145141],f[1145141],n,m,l,r,a1[1145141];
int main(){
	l=read();r=read();
	m=l*r;//计算总面积
	n=read();
	long long ans=0;
	for(int i=1;i<=n;i++){
		a[i]=read();
		a1[i]=a[i]*a[i];
		if(i==1){//特判：最小画框有无可能全部覆盖
			ans=(l-(l%a[i]))*(r-(r%a[i]));
			ans=ans/a1[i];
			if(ans*a1[i]<m){
				cout<<-1;
				exit(0);//=return 0;
			}
		}else{
			long long tmp=(l-(l%a[i]))*(r-(r%a[i]));//tmp表示当前画框可覆盖面积
			ans-=tmp/a1[i-1];//较小画框可换数量
			ans+=tmp/a1[i];//较大画框可换数量
		}
	}
	cout<<ans;
	return 0;
}