B. Chtholly's request

Codeforces

IDCF897B

Time2000ms

Memory256MB

Difficulty—

brute force

English · Original

Chinese · Translation

Formal · Original

%epigraph%%epigraphtext% _— Thanks a lot for today.— I experienced so many great things. — You gave me memories like dreams... But I have to leave now... — One last request, can you... — Help me solve a Codeforces problem? — ...... — What?_%endepigraphtext%%endepigraph%Chtholly has been thinking about a problem for days: If a number is _palindrome_ and length of its decimal representation without leading zeros is even, we call it a zcy number. A number is _palindrome_ means when written in decimal representation, it contains no leading zeros and reads the same forwards and backwards. For example _12321_ and _1221_ are palindromes and _123_ and _12451_ are not. Moreover, _1221_ is zcy number and _12321_ is not. Given integers _k_ and _p_, calculate the sum of the _k_ smallest zcy numbers and output this sum modulo _p_. Unfortunately, Willem isn't good at solving this kind of problems, so he asks you for help! ## Input The first line contains two integers _k_ and _p_ (1 ≤ _k_ ≤ 105, 1 ≤ _p_ ≤ 109). ## Output Output single integer — answer to the problem. [samples] ## Note In the first example, the smallest zcy number is 11, and the second smallest zcy number is 22. In the second example, .

— 我经历了太多美好的事情。 — 你给了我如梦般的回忆……但我现在必须离开了…… — 最后一个请求，你能…… — 帮我解决一个 Codeforces 问题吗？ — ...... — 什么？ Chtholly 已经思考了一个问题好几天了：如果一个数是 _回文数_，且其十进制表示（不含前导零）的长度为偶数，则称其为 zcy 数。一个数是 _回文数_ 指的是，当以十进制表示时，它不包含前导零，且正读和反读完全相同。例如 _12321_ 和 _1221_ 是回文数，而 _123_ 和 _12451_ 不是。此外，_1221_ 是 zcy 数，而 _12321_ 不是。给定整数 #cf_span[k] 和 #cf_span[p]，计算前 #cf_span[k] 个最小的 zcy 数的和，并输出该和对 #cf_span[p] 取模的结果。不幸的是，Willem 不擅长解决这类问题，所以他向你求助！第一行包含两个整数 #cf_span[k] 和 #cf_span[p] #cf_span[(1 ≤ k ≤ 105, 1 ≤ p ≤ 109)]。输出一个整数 —— 问题的答案。在第一个例子中，最小的 zcy 数是 #cf_span[11]，第二小的 zcy 数是 #cf_span[22]。在第二个例子中，。 ## Input 第一行包含两个整数 #cf_span[k] 和 #cf_span[p] #cf_span[(1 ≤ k ≤ 105, 1 ≤ p ≤ 109)]。 ## Output 输出一个整数 —— 问题的答案。 [samples] ## Note 在第一个例子中，最小的 zcy 数是 #cf_span[11]，第二小的 zcy 数是 #cf_span[22]。在第二个例子中，。

**Definitions** Let $ k, p \in \mathbb{Z}^+ $ with $ 1 \leq k \leq 10^5 $, $ 1 \leq p \leq 10^9 $. A **zcy number** is a positive integer that is a palindrome and has an even number of digits in its decimal representation (no leading zeros). Let $ Z = (z_1, z_2, z_3, \dots) $ be the strictly increasing sequence of all zcy numbers, where $ z_1 < z_2 < z_3 < \cdots $. **Constraints** $ 1 \leq k \leq 10^5 $, $ 1 \leq p \leq 10^9 $ **Objective** Compute: $$ \left( \sum_{i=1}^{k} z_i \right) \bmod p $$

Samples

Input #1

2 100

Output #1

Input #2

5 30

Output #2

API Response (JSON)

{
  "problem": {
    "name": "B. Chtholly's request",
    "description": {
      "content": "%epigraph%%epigraphtext% _— Thanks a lot for today.— I experienced so many great things. — You gave me memories like dreams... But I have to leave now... — One last request, can you... — Help me so",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF897B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "%epigraph%%epigraphtext% _— Thanks a lot for today.— I experienced so many great things.\n\n— You gave me memories like dreams... But I have to leave now...\n\n— One last request, can you...\n\n— Help me so...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "— 我经历了太多美好的事情。\n\n— 你给了我如梦般的回忆……但我现在必须离开了……\n\n— 最后一个请求，你能……\n\n— 帮我解决一个 Codeforces 问题吗？\n\n— ...... \n\n— 什么？\n\nChtholly 已经思考了一个问题好几天了：\n\n如果一个数是 _回文数_，且其十进制表示（不含前导零）的长度为偶数，则称其为 zcy 数。一个数是 _回文数_ 指的是，当以十进制表示时，它不包含...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ k, p \\in \\mathbb{Z}^+ $ with $ 1 \\leq k \\leq 10^5 $, $ 1 \\leq p \\leq 10^9 $.  \nA **zcy number** is a positive integer that is a palindrome and has an even number of digits in i...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments