C. Function

Codeforces

IDCF10280C

Time10000ms

Memory64MB

Difficulty—

English · Original

Formal · Original

Define function $f (x) = product limits_{i = 1}^(l e n) (x % 10^i) % (x + 1)$, where $l e n$ represents the digit length of $x$. For example, $f (1023) = (3 * 23 * 23 * 1023) % 1024$. Define function $g (n, m) =$. For example, $g (n, 2) = f (f (n))$. You are given $n$ and $m$, please calculate $\\sum_{i = 1}^{m} g (n, i)$. The input consists of multiple test cases. The first line contains an integer $T$ $(1 <= T <= 20)$ — the number of test cases. The description of the test cases follows. The only line contains two integers $n, m$ $(1 <= n, m <= 10^9)$ . For each test case, print the answer. ## Input The input consists of multiple test cases. The first line contains an integer $T$ $(1 <= T <= 20)$ — the number of test cases. The description of the test cases follows.The only line contains two integers $n, m$ $(1 <= n, m <= 10^9)$ . ## Output For each test case, print the answer. [samples]

**Definitions** Let $ S $ be a string of length $ L $, where $ 7 \leq L \leq 8 \times 10^5 $, composed of uppercase and lowercase letters. Let $ A, B \in \Sigma^* $ be strings such that $ A \neq B $ and $ |A| = |B| $. **Constraints** There exist integers $ n, m, k > 0 $ and a prefix $ a $ of $ A $ with $ 0 \leq |a| < |A| $, such that: $$ S = A^n \cdot B^m \cdot A^k \cdot a $$ **Objective** Find the shortest possible $ A $ and $ B $ (by length $ |A| = |B| $) satisfying the above decomposition. If multiple such pairs exist with minimal $ |A| $, choose the lexicographically smallest pair.

API Response (JSON)

{
  "problem": {
    "name": "C. Function",
    "description": {
      "content": "Define function $f (x) = product limits_{i = 1}^(l e n) (x % 10^i) % (x + 1)$, where $l e n$ represents the digit length of $x$.  For example, $f (1023) = (3 * 23 * 23 * 1023) % 1024$.  Define funct",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 10000,
      "memory_limit": 65536
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10280C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Define function $f (x) = product limits_{i = 1}^(l e n) (x % 10^i) % (x + 1)$, where $l e n$ represents the digit length of $x$. \n\nFor example, $f (1023) = (3 * 23 * 23 * 1023) % 1024$. \n\nDefine funct...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ S $ be a string of length $ L $, where $ 7 \\leq L \\leq 8 \\times 10^5 $, composed of uppercase and lowercase letters.  \nLet $ A, B \\in \\Sigma^* $ be strings such that $ A \\neq B...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments