E. Big Number and Remainder

Codeforces

IDCF795E

Time3000ms

Memory256MB

Difficulty—

brute forcenumber theory

English · Original

Chinese · Translation

Formal · Original

Stepan has a very big positive integer. Let's consider all cyclic shifts of Stepan's integer (if we look at his integer like at a string) which are also integers (i.e. they **do not have** leading zeros). Let's call such shifts as _good shifts_. For example, for the integer 10203 the good shifts are the integer itself 10203 and integers 20310 and 31020. Stepan wants to know the minimum remainder of the division by the given number _m_ among all good shifts. Your task is to determine the minimum remainder of the division by _m_. ## Input The first line contains the integer which Stepan has. The length of Stepan's integer is between 2 and 200 000 digits, inclusive. It is guaranteed that Stepan's integer does not contain leading zeros. The second line contains the integer _m_ (2 ≤ _m_ ≤ 108) — the number by which Stepan divides good shifts of his integer. ## Output Print the minimum remainder which Stepan can get if he divides all good shifts of his integer by the given number _m_. [samples] ## Note In the first example all good shifts of the integer 521 (good shifts are equal to 521, 215 and 152) has same remainder 2 when dividing by 3. In the second example there are only two good shifts: the Stepan's integer itself and the shift by one position to the right. The integer itself is 1001 and the remainder after dividing it by 5 equals 1. The shift by one position to the right equals to 1100 and the remainder after dividing it by 5 equals 0, which is the minimum possible remainder.

Stepan 有一个非常大的正整数。考虑 Stepan 整数的所有循环移位（我们将他的整数视为一个字符串），这些移位仍然是整数（即它们 *不包含* 前导零）。我们将这样的移位称为 _好移位_。例如，对于整数 #cf_span[10203]，好移位包括其本身 #cf_span[10203] 以及整数 #cf_span[20310] 和 #cf_span[31020]。 Stepan 想知道所有好移位对给定数 #cf_span[m] 取模的最小余数。你的任务是确定对 #cf_span[m] 取模的最小余数。第一行包含 Stepan 拥有的整数。该整数的长度在 #cf_span[2] 到 #cf_span[200 000] 位之间（包含两端）。保证 Stepan 的整数不包含前导零。第二行包含整数 #cf_span[m]（#cf_span[2 ≤ m ≤ 108]）——Stepan 对其好移位进行除法的数。请输出 Stepan 对其所有好移位除以给定数 #cf_span[m] 所能得到的最小余数。在第一个例子中，整数 #cf_span[521] 的所有好移位（好移位为 #cf_span[521]、#cf_span[215] 和 #cf_span[152]）在除以 #cf_span[3] 时余数均为 #cf_span[2]。在第二个例子中，只有两个好移位：Stepan 的整数本身和向右移动一位的移位。整数本身是 #cf_span[1001]，除以 #cf_span[5] 的余数为 #cf_span[1]。向右移动一位的移位是 #cf_span[1100]，除以 #cf_span[5] 的余数为 #cf_span[0]，这是可能的最小余数。 ## Input 第一行包含 Stepan 拥有的整数。该整数的长度在 #cf_span[2] 到 #cf_span[200 000] 位之间（包含两端）。保证 Stepan 的整数不包含前导零。第二行包含整数 #cf_span[m]（#cf_span[2 ≤ m ≤ 108]）——Stepan 对其好移位进行除法的数。 ## Output 请输出 Stepan 对其所有好移位除以给定数 #cf_span[m] 所能得到的最小余数。 [samples] ## Note 在第一个例子中，整数 #cf_span[521] 的所有好移位（好移位为 #cf_span[521]、#cf_span[215] 和 #cf_span[152]）在除以 #cf_span[3] 时余数均为 #cf_span[2]。在第二个例子中，只有两个好移位：Stepan 的整数本身和向右移动一位的移位。整数本身是 #cf_span[1001]，除以 #cf_span[5] 的余数为 #cf_span[1]。向右移动一位的移位是 #cf_span[1100]，除以 #cf_span[5] 的余数为 #cf_span[0]，这是可能的最小余数。

Let $ s $ be a string of length $ n $ (where $ 2 \leq n \leq 200{,}000 $) representing a positive integer with no leading zeros. Let $ m $ be an integer such that $ 2 \leq m \leq 10^8 $. Define a *good shift* as a cyclic shift of $ s $ that does not start with '0'. Let $ S $ be the set of all such good shifts, interpreted as integers. For each $ t \in S $, let $ v(t) $ denote the integer value of $ t $. Compute: $$ \min_{t \in S} \left( v(t) \bmod m \right) $$

Samples

Input #1

521
3

Output #1

Input #2

1001
5

Output #2

Input #3

5678901234567890123456789
10000

Output #3

API Response (JSON)

{
  "problem": {
    "name": "E. Big Number and Remainder",
    "description": {
      "content": "Stepan has a very big positive integer. Let's consider all cyclic shifts of Stepan's integer (if we look at his integer like at a string) which are also integers (i.e. they **do not have** leading ze",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF795E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Stepan has a very big positive integer.\n\nLet's consider all cyclic shifts of Stepan's integer (if we look at his integer like at a string) which are also integers (i.e. they **do not have** leading ze...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Stepan 有一个非常大的正整数。\n\n考虑 Stepan 整数的所有循环移位（我们将他的整数视为一个字符串），这些移位仍然是整数（即它们 *不包含* 前导零）。我们将这样的移位称为 _好移位_。例如，对于整数 #cf_span[10203]，好移位包括其本身 #cf_span[10203] 以及整数 #cf_span[20310] 和 #cf_span[31020]。\n\nStepan 想知道所有...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "Let $ s $ be a string of length $ n $ (where $ 2 \\leq n \\leq 200{,}000 $) representing a positive integer with no leading zeros.\n\nLet $ m $ be an integer such that $ 2 \\leq m \\leq 10^8 $.\n\nDefine a *g...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments