Problem

题目描述

给定两个整数 \(n,m\) 问有多少三元组 \((x,y,z)\) 满足：

• \(0\le x,y,z\le n\)
• \(x+y+z=m\)

输入格式

一行给出两个整数 \(n,m\) 。

输出格式

一个整数，代表答案。

Example&Prompt

输入输出样例

样例\(1\)：
输入：$2\ 2\ \ \ $ 输出：\(6\)
样例\(2\)：
输入：$3\ 15\ $ 输出：\(1\)

数据范围

对于\(20\%\)的数据，满足\(1\le n\le 100\)。
对于\(50\%\)的数据，满足\(1\le n\le 10^4\)。
对于\(100\%\)的数据，满足\(1\le n\le 10^7,0\le m\le3n\)。

Solution1（20pts）

暴力枚举\(x,y,z\)，再判断合不合法，时间复杂度为\(O(n^3)\)。

Solution2（50pts）

暴力枚举\(x,y\)，根据条件\(2\)算出\(z\)，再判断合不合法，时间复杂度为\(O(n^2)\)。

Solution3（100pts）

暴力枚举\(x\)，再求出\(y,z\)的所有可能性。

那如何求\(y,z\)的所有可能性呢？不妨先令\(k=m-x\)，因为条件\(1\)，所以当\(k< 0\)时没有合法的解，只要讨论\(k\ge 0\)的情况。

首先先看一种简单的情况：\(n\ge k\)

根据条件\(2\)，我们有\(y+z=k\)，因为\(n\ge k\)，所以不存在不合法的结果。

因此，我们就是要求两个自然数之和为\(k\)的数量，这个很明显是\(k+1\)种，举个例子：

\[4=0+4=1+3=2+2=3+1=4+0 \]

其实也就是\(k=i+(k-i)(0\le i\le k)\)，共\(k+1\)种可能。

然后再看\(n<k\)的情况，我们依旧有\(y+z=k\)，但此时可能有不合法结果，甚至没有合法结果。

我们先设\(y=n\)，此时\(z=k-n=m-2n\)为最小值，如果\(z>n\)，那么代表没有合法结果，因为最小的可能也不符合要求，也就没有符合要求的结果了。

然后考虑有不合法结果也有合法结果，根据上面的例子\(4\)我们可以看出，分解的两端（即\(y,z\)分别取较大值时)最可能不符合要求，因此我们只要找出有多少不符合要求的值，再用总情况减去，就知道了有多少合法值。

很明显，从\(k=i+(k-i)(0\le i\le k)\)可以看出\(i>n\)不符合情况的数量是\(k-n\)，\(k-i\)不符合情况的数量也是\(k-n\)（正好与\(i\)不符合情况相反）。

总情况仍是\(k+1\)，因此，这时候符合情况的数量就是\(k+1-(k-n)* 2=2n-k+1\)。

我们把所有情况加起来就是答案了，时间复杂度为\(O(n)\)。

Code

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,m,ans=0;
    scanf("%d%d",&n,&m);
    for(int i=0;i<=n;i++)
    {
        int k=m-i,j=0;
        if(k>=0)
        {
            if(k>n)
            {
                if(k-n>n)
                j=0;
                else
                j=2*n-k+1;
            }
            else
            j=k+1;
        }
        ans+=j;
    }
    printf("%d",ans);
    return 0;
}