1996D.md (1355B)
1 Source: https://codeforces.com/problemset/problem/1996/D 2 3 D. Fun 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Counting is Fun! 22 23 — satyam343 24 25 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$. 26 27 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$. 28 29 Input 30 31 The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. 32 33 Each test case contains two integers $n$ and $x$ ($1 \leq n,x \leq 10^6$). 34 35 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$. 36 37 Output 38 39 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$. 40 41 Example 42 43 Input 44 45 ``` 46 4 47 48 7 4 49 50 10 5 51 52 7 1000 53 54 900000 400000 55 ``` 56 57 Output 58 59 ``` 60 4 61 10 62 7 63 1768016938 64 ``` 65 66 Note 67 68 In the first test case, the triplets are ($1, 1, 1$), ($1, 1, 2$), ($1, 2, 1$), and ($2, 1, 1$). 69 70 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$).