codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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$).