{"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## Input\n\nThe only line contains four integers $a,b,p,x$ ($2 \\leq p \\leq 10^6+3$, $1 \\leq a,b &lt; p$, $1 \\leq x \\leq 10^{12}$). It is guaranteed that $p$ is a prime.\n\n## Output\n\nPrint a single integer: the number of possible answers $n$.\n\n[samples]\n\n## Note\n\nIn the first sample, we can see that $n=2$ and $n=8$ are possible answers.","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.eq x lt.eq 10^(12)$）。保证 $p$ 是一个质数。\n\n输出一个整数：满足条件的 $n$ 的个数。\n\n在第一个样例中，我们可以看到 $n = 2$ 和 $n = 8$ 是可能的答案。\n\n## Input\n\n仅一行包含四个整数 $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## Output\n\n输出一个整数：满足条件的 $n$ 的个数。\n\n[samples]\n\n## Note\n\n在第一个样例中，我们可以看到 $n = 2$ 和 $n = 8$ 是可能的答案。","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**Constraints**  \n- $ p $ is prime.  \n- $ 1 \\leq a, b < p $.  \n- $ 1 \\leq x \\leq 10^{12} $.  \n\n**Objective**  \nCount the number of integers $ n \\in \\{1, 2, \\dots, x\\} $ such that:  \n$$\nn \\cdot a^n \\equiv b \\pmod{p}\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF919E","tags":["chinese remainder theorem","math","number theory"],"sample_group":[["2 3 5 8","2"],["4 6 7 13","1"],["233 233 10007 1","1"]],"created_at":"2026-03-03 11:00:39"}}