题解：P10090 [ROIR 2022 Day 2] 幼儿园的新年

题目传送门

写一篇和其他题解不一样的解题思路（个人感觉更好理解）。

我们用一个二维矩阵来观察 x,y 之和的关系，如下图，可以发现矩阵对角线上的 x,y 之和相等，所以我们就可以找到满足条件的 x+y 为 n 的倍数的所有情况。

举例：2 4 6

如下图：

我们要求的是标红的矩阵里的所有 2 的倍数的数字个数，即红色矩阵里画斜线数字的数量，蓝色斜线是全部在要求的矩阵里的，红色斜线是部分在要求的矩阵里的，我们可以先求有颜色的大三角形里 2 的倍数的数字的个数，再减去两个标黄色的小三角形里 2 的倍数的数字的个数，可以看出，每个三角形里的不同的数字的个数组成了等差数列，所以我们可以直接用等差数列来求和。

代码如下：

CPP

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll t;
int main(){
	scanf("%lld",&t);
	while(t--){
		ll n,a,b;
		ll ans=0;
		scanf("%lld%lld%lld",&n,&a,&b);
		ll minn=min(a,b);
		ll maxn=max(a,b);
		ll end=(minn/n+1)*n;//短的那一部分超出矩阵部分的第一个n的倍数 
		ll end2=(maxn/n+1)*n;//长的那一部分超出矩阵部分的第一个n的倍数 
		ll x=(a+b);//要求的这个矩阵里最大的值 
		if(n<=x)ans=((n+1)+(n+1+(x-n)/n*n))*((x-n)/n+1)/2;//先求出所有的数量 ,如果n本来就比矩阵里最大的数大，那么答案为0 
		if(end<=x){//需要判断 
			ans-=(((end-minn)+(end-minn+(x-end)/n*n))*((x-end)/n+1))/2;
		}//分别减去多余的部分 
		if(end2<=x){//需要判断 
			ans-=(((end2-maxn)+(end2-maxn+(x-end2)/n*n))*((x-end2)/n+1))/2;
		}//分别减去多余的部分 
		printf("%lld\n",ans);
	}
	return 0;
}

题解：P10090 [ROIR 2022 Day 2] 幼儿园的新年

文章操作

题目传送门

相关推荐

评论

题解：P10090 [ROIR 2022 Day 2] 幼儿园的新年