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

Jx663358 · 2024-11-19 16:00:16 · 题解

题目传送门

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

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

举例：2 4 6

如下图 ：

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

代码如下：

#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;
}