Dirichlet $$$k$$$-th root

Codeforces

IDCF10247C

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

_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 : {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}}) .$$ We define the $k$-th power of an function $g = f^k$ by $$ f^{k}=\underbrace {f * \dots * f} _{k~{\textrm {times}}}.$$ In 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$. Moreover, 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$. The 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$). If 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. ## Input The 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$). ## Output If 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. [samples]

**Definitions** Let $ p = 998244353 $. Let $ n, k \in \mathbb{Z} $ with $ 2 \leq n \leq 10^5 $, $ 1 \leq k < p $. Let $ g: \{1, 2, \dots, n\} \to \mathbb{Z}/p\mathbb{Z} $ be a function with $ g(1) = 1 $. Let $ 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. **Constraints** 1. $ g(i) \in \mathbb{Z}/p\mathbb{Z} $ for all $ i \in \{1, \dots, n\} $, and $ g(1) = 1 $. 2. $ f(1) = 1 $. 3. All operations are performed modulo $ p $. 4. For all $ m \in \{1, \dots, n\} $: $$ g(m) = \sum_{d \mid m} f(d) \cdot f^{*(k-1)}\left(\frac{m}{d}\right) \mod p $$ **Objective** Find a function $ f $ satisfying $ f^{*k} = g $, or output $-1$ if no such $ f $ exists.

API Response (JSON)

{
  "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 ...",
      "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(...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments