183184

AtCoder

IDabc428_d

Time2500ms

Memory256MB

Difficulty—

For positive integers $x$ and $y$, define $f(x,y)$ as follows: * Let $z$ be the string obtained by interpreting $x,y$ in decimal notation as strings and concatenating them in this order. Let $f(x,y)$ be the value when $z$ is interpreted as an integer in decimal notation. For example, $f(3,14)=314,\ f(100,3)=1003$. You are given positive integers $C$ and $D$. Find the number of integers $x$ that satisfy the following conditions: * $1 \leq x \leq D$ * $f(C, C+x)$ is a perfect square. You are given $T$ test cases, find the answer for each of them. ## Constraints * $1 \leq T \leq 3 \times 10^5$ * $1 \leq C \leq 2 \times 10^8$ * $1 \leq D \leq 5 \times 10^9$ * All input values are integers. ## Input The input is given from Standard Input in the following format: $T$ $\textrm{case}_1$ $\textrm{case}_2$ $\vdots$ $\textrm{case}_T$ $\textrm{case}_i$ represents the $i$\-th test case. Each test case is given in the following format: $C$ $D$ [samples]

Samples

Input #1

4
4 80
183 5000
18 10
824 5000000000

Output #1

3
2
0
1421

For the first test case, there are three values of $x$ that satisfy the conditions: $x = 5, 37, 80$.

*   When $x=5$, $f(C, C+5) = f(4,9) = 49 = 7^2$
*   When $x=37$, $f(C, C+37) = f(4,41) = 441 = 21^2$
*   When $x=80$, $f(C, C+80) = f(4,84) = 484 = 22^2$

For the second test case, there are two values of $x$ that satisfy the conditions: $x = 1, 3133$.

*   When $x=1$, $f(C, C+1) = f(183,184) = 183184 = 428^2$
*   When $x=3133$, $f(C, C+3133) = f(183,3316) = 1833316 = 1354^2$

For the third test case, there are zero values of $x$ that satisfy the conditions.
For the fourth test case, there are $1421$ values of $x$ that satisfy the conditions.

API Response (JSON)

{
  "problem": {
    "name": "183184",
    "description": {
      "content": "For positive integers $x$ and $y$, define $f(x,y)$ as follows: *   Let $z$ be the string obtained by interpreting $x,y$ in decimal notation as strings and concatenating them in this order. Let $f(x,y",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2500,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc428_d"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "For positive integers $x$ and $y$, define $f(x,y)$ as follows:\n\n*   Let $z$ be the string obtained by interpreting $x,y$ in decimal notation as strings and concatenating them in this order. Let $f(x,y...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments