E. Congruence Equation

Codeforces

IDCF919E

Time3000ms

Memory256MB

Difficulty—

chinese remainder theoremmathnumber theory

English · Original

Chinese · Translation

Formal · Original

Given an integer $x$. Your task is to find out how many positive integers $n$ ($1 \leq n \leq x$) satisfy n \\cdot a^n \\equiv b \\quad (\\textrm{mod}\\;p), where $a, b, p$ are all known constants. ## Input The only line contains four integers $a,b,p,x$ ($2 \leq p \leq 10^6+3$, $1 \leq a,b < p$, $1 \leq x \leq 10^{12}$). It is guaranteed that $p$ is a prime. ## Output Print a single integer: the number of possible answers $n$. [samples] ## Note In the first sample, we can see that $n=2$ and $n=8$ are possible answers.

给定一个整数 $x$。你的任务是找出有多少个正整数 $n$（$1 lt.eq n lt.eq x$）满足 $$n \cdot a^n \equiv b \quad (\textrm{mod}\;p),$$ 其中 $a, b, p$ 均为已知常数。仅一行包含四个整数 $a, b, p, x$（$2 lt.eq p lt.eq 10^6 + 3$，$1 lt.eq a, b < p$，$1 lt.eq x lt.eq 10^(12)$）。保证 $p$ 是一个质数。输出一个整数：满足条件的 $n$ 的个数。在第一个样例中，我们可以看到 $n = 2$ 和 $n = 8$ 是可能的答案。 ## Input 仅一行包含四个整数 $a, b, p, x$（$2 lt.eq p lt.eq 10^6 + 3$，$1 lt.eq a, b < p$，$1 lt.eq x lt.eq 10^(12)$）。保证 $p$ 是一个质数。 ## Output 输出一个整数：满足条件的 $n$ 的个数。 [samples] ## Note 在第一个样例中，我们可以看到 $n = 2$ 和 $n = 8$ 是可能的答案。

**Definitions** Let $ a, b, p \in \mathbb{Z} $ be given constants with $ p $ prime, $ 2 \leq p \leq 10^6 + 3 $, $ 1 \leq a, b < p $. Let $ x \in \mathbb{Z} $ with $ 1 \leq x \leq 10^{12} $. **Constraints** - $ p $ is prime. - $ 1 \leq a, b < p $. - $ 1 \leq x \leq 10^{12} $. **Objective** Count the number of integers $ n \in \{1, 2, \dots, x\} $ such that: $$ n \cdot a^n \equiv b \pmod{p} $$

Samples

Input #1

2 3 5 8

Output #1

Input #2

4 6 7 13

Output #2

Input #3

233 233 10007 1

Output #3

API Response (JSON)

{
  "problem": {
    "name": "E. Congruence Equation",
    "description": {
      "content": "Given an integer $x$. Your task is to find out how many positive integers $n$ ($1 \\leq n \\leq x$) satisfy n \\\\cdot a^n \\\\equiv b \\\\quad (\\\\textrm{mod}\\\\;p), where $a, b, p$ are all known constants.",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF919E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Given an integer $x$. Your task is to find out how many positive integers $n$ ($1 \\leq n \\leq x$) satisfy n \\\\cdot a^n \\\\equiv b \\\\quad (\\\\textrm{mod}\\\\;p), where $a, b, p$ are all known constants.\n\n#...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "给定一个整数 $x$。你的任务是找出有多少个正整数 $n$（$1 lt.eq n lt.eq x$）满足 $$n \\cdot a^n \\equiv b \\quad (\\textrm{mod}\\;p),$$ 其中 $a, b, p$ 均为已知常数。\n\n仅一行包含四个整数 $a, b, p, x$（$2 lt.eq p lt.eq 10^6 + 3$，$1 lt.eq a, b < p$，$1 lt....",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ a, b, p \\in \\mathbb{Z} $ be given constants with $ p $ prime, $ 2 \\leq p \\leq 10^6 + 3 $, $ 1 \\leq a, b < p $.  \nLet $ x \\in \\mathbb{Z} $ with $ 1 \\leq x \\leq 10^{12} $.  \n\n**C...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments