A. Modular Exponentiation

Codeforces

IDCF913A

Time1000ms

Memory256MB

Difficulty—

implementationmath

English · Original

Chinese · Translation

Formal · Original

The following problem is well-known: given integers _n_ and _m_, calculate <center>,</center>where 2_n_ = 2·2·...·2 (_n_ factors), and denotes the remainder of division of _x_ by _y_. You are asked to solve the "reverse" problem. Given integers _n_ and _m_, calculate <center>.</center> ## Input The first line contains a single integer _n_ (1 ≤ _n_ ≤ 108). The second line contains a single integer _m_ (1 ≤ _m_ ≤ 108). ## Output Output a single integer — the value of . [samples] ## Note In the first example, the remainder of division of 42 by 24 = 16 is equal to 10. In the second example, 58 is divisible by 21 = 2 without remainder, and the answer is 0.

以下问题是众所周知的：给定整数 #cf_span[n] 和 #cf_span[m]，计算其中 #cf_span[2n = 2·2·...·2]（#cf_span[n] 个因子），且表示 #cf_span[x] 除以 #cf_span[y] 的余数。你被要求解决这个“逆向”问题。给定整数 #cf_span[n] 和 #cf_span[m]，计算第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 108]）。第二行包含一个整数 #cf_span[m]（#cf_span[1 ≤ m ≤ 108]）。请输出一个整数 —— 的值。在第一个示例中，42 除以 #cf_span[24 = 16] 的余数等于 10。在第二个示例中，58 能被 #cf_span[21 = 2] 整除，余数为 0。 ## Input 第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 108]）。第二行包含一个整数 #cf_span[m]（#cf_span[1 ≤ m ≤ 108]）。 ## Output 请输出一个整数 —— 的值。 [samples] ## Note 在第一个示例中，42 除以 #cf_span[24 = 16] 的余数等于 10。在第二个示例中，58 能被 #cf_span[21 = 2] 整除，余数为 0。

Given integers $ n $ and $ m $, compute: $$ 2^n \bmod m $$

Samples

Input #1

4
42

Output #1

Input #2

1
58

Output #2

Input #3

98765432
23456789

Output #3

23456789

API Response (JSON)

{
  "problem": {
    "name": "A. Modular Exponentiation",
    "description": {
      "content": "The following problem is well-known: given integers _n_ and _m_, calculate <center>,</center>where 2_n_ = 2·2·...·2 (_n_ factors), and denotes the remainder of division of _x_ by _y_. You are asked ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF913A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "The following problem is well-known: given integers _n_ and _m_, calculate\n\n<center>,</center>where 2_n_ = 2·2·...·2 (_n_ factors), and denotes the remainder of division of _x_ by _y_.\n\nYou are asked ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "以下问题是众所周知的：给定整数 #cf_span[n] 和 #cf_span[m]，计算\n\n其中 #cf_span[2n = 2·2·...·2]（#cf_span[n] 个因子），且  表示 #cf_span[x] 除以 #cf_span[y] 的余数。\n\n你被要求解决这个“逆向”问题。给定整数 #cf_span[n] 和 #cf_span[m]，计算\n\n第一行包含一个整数 #cf_span[n...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "Given integers $ n $ and $ m $, compute:\n\n$$\n2^n \\bmod m\n$$...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments