G. Power Substring

Codeforces

IDCF913G

Time2000ms

Memory256MB

Difficulty—

mathnumber theory

English · Original

Chinese · Translation

Formal · Original

You are given _n_ positive integers _a_1, _a_2, ..., _a__n_. For every _a__i_ you need to find a positive integer _k__i_ such that the decimal notation of 2_k__i_ contains the decimal notation of _a__i_ as a substring among its last _min_(100, _length_(2_k__i_)) digits. Here _length_(_m_) is the length of the decimal notation of _m_. Note that you don't have to minimize _k__i_. The decimal notations in this problem do not contain leading zeros. ## Input The first line contains a single integer _n_ (1 ≤ _n_ ≤ 2 000) — the number of integers _a__i_. Each of the next _n_ lines contains a positive integer _a__i_ (1 ≤ _a__i_ < 1011). ## Output Print _n_ lines. The _i_\-th of them should contain a positive integer _k__i_ such that the last _min_(100, _length_(2_k__i_)) digits of 2_k__i_ contain the decimal notation of _a__i_ as a substring. Integers _k__i_ must satisfy 1 ≤ _k__i_ ≤ 1050. It can be shown that the answer always exists under the given constraints. If there are multiple answers, print any of them. [samples]

给定 #cf_span[n] 个正整数 #cf_span[a1, a2, ..., an]。对于每个 #cf_span[ai]，你需要找到一个正整数 #cf_span[ki]，使得 #cf_span[2ki] 的十进制表示在其最后 #cf_span[min(100, length(2ki))] 位中包含 #cf_span[ai] 的十进制表示作为子串。这里 #cf_span[length(m)] 表示 #cf_span[m] 的十进制表示的长度。注意，你无需最小化 #cf_span[ki]。本题中的十进制表示不包含前导零。第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 2 000]) —— 整数 #cf_span[ai] 的个数。接下来的 #cf_span[n] 行，每行包含一个正整数 #cf_span[ai] (#cf_span[1 ≤ ai < 1011])。请输出 #cf_span[n] 行。第 #cf_span[i] 行应包含一个正整数 #cf_span[ki]，使得 #cf_span[2ki] 的最后 #cf_span[min(100, length(2ki))] 位中包含 #cf_span[ai] 的十进制表示作为子串。要求 #cf_span[ki] 满足 #cf_span[1 ≤ ki ≤ 1050]。可以证明，在给定约束下答案一定存在。如果存在多个答案，输出任意一个即可。 ## Input 第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 2 000]) —— 整数 #cf_span[ai] 的个数。接下来的 #cf_span[n] 行，每行包含一个正整数 #cf_span[ai] (#cf_span[1 ≤ ai < 1011])。 ## Output 请输出 #cf_span[n] 行。第 #cf_span[i] 行应包含一个正整数 #cf_span[ki]，使得 #cf_span[2ki] 的最后 #cf_span[min(100, length(2ki))] 位中包含 #cf_span[ai] 的十进制表示作为子串。要求 #cf_span[ki] 满足 #cf_span[1 ≤ ki ≤ 1050]。可以证明，在给定约束下答案一定存在。如果存在多个答案，输出任意一个即可。 [samples]

Let $ n \in \mathbb{N} $, $ 1 \leq n \leq 2000 $. Given $ a_1, a_2, \dots, a_n \in \mathbb{N} $, with $ 1 \leq a_i < 10^{11} $ for all $ i \in \{1, 2, \dots, n\} $. For each $ a_i $, find $ k_i \in \mathbb{N} $, $ 1 \leq k_i \leq 10^{50} $, such that the decimal representation of $ 2^{k_i} $, when restricted to its last $ \min(100, \lfloor \log_{10}(2^{k_i}) \rfloor + 1) $ digits, contains the decimal representation of $ a_i $ as a contiguous substring. That is, let $ d(m) $ denote the decimal representation of a positive integer $ m $ (without leading zeros). Let $ L_i = \min\left(100, \left\lfloor \log_{10}(2^{k_i}) \right\rfloor + 1\right) $. Then, $ d(a_i) $ must be a substring of the suffix of $ d(2^{k_i}) $ of length $ L_i $. Output $ k_1, k_2, \dots, k_n $.

Samples

Input #1

2
8
2

Output #1

3
1

Input #2

2
3
4857

Output #2

5
20

API Response (JSON)

{
  "problem": {
    "name": "G. Power Substring",
    "description": {
      "content": "You are given _n_ positive integers _a_1, _a_2, ..., _a__n_. For every _a__i_ you need to find a positive integer _k__i_ such that the decimal notation of 2_k__i_ contains the decimal notation of _a_",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF913G"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given _n_ positive integers _a_1, _a_2, ..., _a__n_.\n\nFor every _a__i_ you need to find a positive integer _k__i_ such that the decimal notation of 2_k__i_ contains the decimal notation of _a_...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "给定 #cf_span[n] 个正整数 #cf_span[a1, a2, ..., an]。\n\n对于每个 #cf_span[ai]，你需要找到一个正整数 #cf_span[ki]，使得 #cf_span[2ki] 的十进制表示在其最后 #cf_span[min(100, length(2ki))] 位中包含 #cf_span[ai] 的十进制表示作为子串。这里 #cf_span[length(m)...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "Let $ n \\in \\mathbb{N} $, $ 1 \\leq n \\leq 2000 $.  \nGiven $ a_1, a_2, \\dots, a_n \\in \\mathbb{N} $, with $ 1 \\leq a_i < 10^{11} $ for all $ i \\in \\{1, 2, \\dots, n\\} $.\n\nFor each $ a_i $, find $ k_i \\in...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments