{"problem":{"name":"Dirichlet $$$k$$$-th root","description":{"content":"_Mathematician Pang_ learned Dirichlet convolution during the previous camp. However, compared with deep reinforcement learning, it's too easy for him. Therefore, he did something special.  If $f, g ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10247C"},"statements":[{"statement_type":"Markdown","content":"_Mathematician Pang_ learned Dirichlet convolution during the previous camp. However, compared with deep reinforcement learning, it's too easy for him. Therefore, he did something special. \n\nIf $f, g : {1, 2, \\\\dots, n} arrow.r ZZ$ are two functions from the positive integers to the integers, the Dirichlet convolution $f * g$ is a new function defined by: $$(f * g)(n) =\\sum_{d \\mid n}f(d)g ({\\frac {n}{d}}) .$$\n\nWe define the $k$-th power of an function $g = f^k$ by $$ f^{k}=\\underbrace {f * \\dots * f} _{k~{\\textrm {times}}}.$$\n\nIn this problem, we want to solve the inverse problem: Given $g$ and $k$, you need to find a function $f$ such that $g = f^k$.\n\nMoreover, there is an additional constraint that $f (1)$ and $g (1)$ must equal to $1$. And all the arithmetic operations are done on $FF_p$ where $p = 998244353$, which means that in the Dirichlet convolution, $(f * g) (n) = (sum_(d mid n) f (d) g (frac(n, d))) bmod p$.\n\nThe first line contains two integers $n$ and $k med (2 <= n <= 10^5, 1 <= k < 998244353)$ .\n\nThe second line contains n integers $g (1), g (2),..., g (n)$ ($0 <= g (i) < 998244353, g (1) = 1$).\n\nIf there is no solution, output $-1$.\n\nOtherwise, output $f (1), f (2),..., f (n)$ ($0 <= f (i) < 998244353, f (1) = 1$). If there are multiple solutions, print anyone.\n\n## Input\n\nThe first line contains two integers $n$ and $k med (2 <= n <= 10^5, 1 <= k < 998244353)$ .The second line contains n integers $g (1), g (2),..., g (n)$ ($0 <= g (i) < 998244353, g (1) = 1$).\n\n## Output\n\nIf there is no solution, output $-1$.Otherwise, output $f (1), f (2),..., f (n)$ ($0 <= f (i) < 998244353, f (1) = 1$). If there are multiple solutions, print anyone.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ p = 998244353 $.  \nLet $ n, k \\in \\mathbb{Z} $ with $ 2 \\leq n \\leq 10^5 $, $ 1 \\leq k < p $.  \nLet $ g: \\{1, 2, \\dots, n\\} \\to \\mathbb{Z}/p\\mathbb{Z} $ be a function with $ g(1) = 1 $.  \nLet $ f: \\{1, 2, \\dots, n\\} \\to \\mathbb{Z}/p\\mathbb{Z} $ be the unknown function with $ f(1) = 1 $, such that $ g = f^{*k} $, where $ f^{*k} $ denotes the $ k $-fold Dirichlet convolution of $ f $ with itself.\n\n**Constraints**  \n1. $ g(i) \\in \\mathbb{Z}/p\\mathbb{Z} $ for all $ i \\in \\{1, \\dots, n\\} $, and $ g(1) = 1 $.  \n2. $ f(1) = 1 $.  \n3. All operations are performed modulo $ p $.  \n4. For all $ m \\in \\{1, \\dots, n\\} $:  \n   $$\n   g(m) = \\sum_{d \\mid m} f(d) \\cdot f^{*(k-1)}\\left(\\frac{m}{d}\\right) \\mod p\n   $$\n\n**Objective**  \nFind a function $ f $ satisfying $ f^{*k} = g $, or output $-1$ if no such $ f $ exists.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10247C","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}