G. Math, math everywhere

Codeforces

IDCF765G

Time5000ms

Memory512MB

Difficulty—

brute forcedpmathmeet-in-the-middlenumber theory

English · Original

Chinese · Translation

Formal · Original

_If you have gone that far, you'll probably skip unnecessary legends anyway..._ You are given a binary string and an integer . Find the number of integers _k_, 0 ≤ _k_ < _N_, such that for all _i_ = 0, 1, ..., _m_ - 1 Print the answer modulo 109 + 7. ## Input In the first line of input there is a string _s_ consisting of 0's and 1's (1 ≤ |_s_| ≤ 40). In the next line of input there is an integer _n_ (1 ≤ _n_ ≤ 5·105). Each of the next _n_ lines contains two space-separated integers _p__i_, α_i_ (1 ≤ _p__i_, α_i_ ≤ 109, _p__i_ is prime). All _p__i_ are distinct. ## Output A single integer — the answer to the problem. [samples]

_如果你已经走到这一步，你大概会直接跳过无用的背景故事……_ 给你一个二进制字符串 $s$ 和一个整数 $N$。求满足 $0 \leq k < N$ 的整数 $k$ 的个数，使得对所有 $i = 0, 1, \dots, m - 1$，都有输入的第一行是一个由 $0$ 和 $1$ 组成的字符串 $s$（$1 \leq |s| \leq 40$）。第二行是一个整数 $n$（$1 \leq n \leq 5 \cdot 10^5$）。接下来的 $n$ 行，每行包含两个用空格分隔的整数 $p_i, \alpha_i$（$1 \leq p_i, \alpha_i \leq 10^9$，$p_i$ 是质数）。所有 $p_i$ 互不相同。输出一个整数 —— 本题的答案。 ## Input 在第一行输入中，有一个由 $0$ 和 $1$ 组成的字符串 $s$（$1 \leq |s| \leq 40$）。在下一行输入中，有一个整数 $n$（$1 \leq n \leq 5 \cdot 10^5$）。接下来的 $n$ 行，每行包含两个用空格分隔的整数 $p_i, \alpha_i$（$1 \leq p_i, \alpha_i \leq 10^9$，$p_i$ 是质数）。所有 $p_i$ 互不相同。 ## Output 一个整数 —— 本题的答案。 [samples]

Given a binary string $ s $ of length $ m $ ($ 1 \leq m \leq 40 $) and an integer $ n $ ($ 1 \leq n \leq 5 \cdot 10^5 $), along with $ n $ distinct prime pairs $ (p_i, \alpha_i) $ where $ 1 \leq p_i, \alpha_i \leq 10^9 $, define: Let $ K = \prod_{i=1}^n p_i^{\alpha_i} $. For each integer $ k \in [0, K-1] $, let $ b_k $ be the binary string of length $ m $ formed by the least significant $ m $ bits of $ k $ (padded with leading zeros if necessary). Count the number of integers $ k \in [0, K-1] $ such that $ b_k = s $. --- **Formal Statement:** Let $ s \in \{0,1\}^m $, $ K = \prod_{i=1}^n p_i^{\alpha_i} $. Define the function $ f: \mathbb{Z} \to \{0,1\}^m $ by $$ f(k) = \text{the } m\text{-bit binary representation of } k \bmod 2^m \text{ (with leading zeros)}. $$ Compute: $$ \left| \left\{ k \in [0, K-1] \mid f(k) = s \right\} \right| $$

Samples

Input #1

Output #1

Input #2

Output #2

Input #3

1011
1
3 1000000000

Output #3

411979884

API Response (JSON)

{
  "problem": {
    "name": "G. Math, math everywhere",
    "description": {
      "content": "_If you have gone that far, you'll probably skip unnecessary legends anyway..._ You are given a binary string and an integer . Find the number of integers _k_, 0 ≤ _k_ < _N_, such that for all _i_ = ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 5000,
      "memory_limit": 524288
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF765G"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "_If you have gone that far, you'll probably skip unnecessary legends anyway..._\n\nYou are given a binary string and an integer . Find the number of integers _k_, 0 ≤ _k_ < _N_, such that for all _i_ = ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "_如果你已经走到这一步，你大概会直接跳过无用的背景故事……_\n\n给你一个二进制字符串 $s$ 和一个整数 $N$。求满足 $0 \\leq k < N$ 的整数 $k$ 的个数，使得对所有 $i = 0, 1, \\dots, m - 1$，都有\n\n输入的第一行是一个由 $0$ 和 $1$ 组成的字符串 $s$（$1 \\leq |s| \\leq 40$）。\n\n第二行是一个整数 $n$（$1 \\leq ...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "Given a binary string $ s $ of length $ m $ ($ 1 \\leq m \\leq 40 $) and an integer $ n $ ($ 1 \\leq n \\leq 5 \\cdot 10^5 $), along with $ n $ distinct prime pairs $ (p_i, \\alpha_i) $ where $ 1 \\leq p_i, ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments