Fun

题面翻译

Counting is Fun!

给定两个整数 $n$ 和 $x$（$1\le n,x\le 10^6$），求满足 $ab + ac + bc \le n$ 且 $a + b + c \le x$ 的正整数三元组 $(a,b,c)$ 的个数。

请注意，三元组是有序的。例如，$(1, 1, 2)$ 和 $(1, 2, 1)$ 是不同的三元组。$a,b,c$ 必须严格大于 $0$ 。

Translated by PineappleSummer.

题目描述

Counting is Fun!

— satyam343

Given two integers $ n $ and $ x $ , find the number of triplets ( $ a,b,c $ ) of positive integers such that $ ab + ac + bc \le n $ and $ a + b + c \le x $ .

Note that order matters (e.g. ( $ 1, 1, 2 $ ) and ( $ 1, 2, 1 $ ) are treated as different) and $ a $ , $ b $ , $ c $ must be strictly greater than $ 0 $ .

输入格式

The first line contains a single integer $ t $ ( $ 1 \leq t \leq 10^4 $ ) — the number of test cases.

Each test case contains two integers $ n $ and $ x $ ( $ 1 \leq n,x \leq 10^6 $ ).

It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^6 $ and that the sum of $ x $ over all test cases does not exceed $ 10^6 $ .

输出格式

Output a single integer — the number of triplets ( $ a,b,c $ ) of positive integers such that $ ab + ac + bc \le n $ and $ a + b + c \le x $ .

样例 #1

样例输入 #1

4
7 4
10 5
7 1000
900000 400000

样例输出 #1

4
10
7
1768016938

提示

In the first test case, the triplets are ( $ 1, 1, 1 $ ), ( $ 1, 1, 2 $ ), ( $ 1, 2, 1 $ ), and ( $ 2, 1, 1 $ ).

In the second test case, the triplets are ( $ 1, 1, 1 $ ), ( $ 1, 1, 2 $ ), ( $ 1, 1, 3 $ ), ( $ 1, 2, 1 $ ), ( $ 1, 2, 2 $ ), ( $ 1, 3, 1 $ ), ( $ 2, 1, 1 $ ), ( $ 2, 1, 2 $ ), ( $ 2, 2, 1 $ ), and ( $ 3, 1, 1 $ ).

此种题用暴力枚举，先枚举一个，另外一个缩短范围去枚举

const int N = 4e5 + 10;
int a[N];
int n, x;
int cheak(int i,int j,int k)
{
    if (i + j + k <= x && i * j + i * k + j * k <= n) return 1;
    else return 0;
}
void solve()
{
    cin >> n >> x;
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j * i <= n && j + i <= x; j++)
        {
            int k = x - i - j;
            if (k > 0)
            {
                int l = 1, r = k;
                int daan = 0;
                while (l <= r)
                {
                    int mid = (l + r) / 2;
                    if (cheak(i,j,mid))
                    {
                        daan = mid;
                        l = mid + 1;
                    }
                    else r = mid - 1;
                }
                ans += daan;
            }
        }
    }
    cout << ans << '\n';
}