H. Riana and Humongous Numbers

Codeforces

IDCF10255H

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Riana got really bored one day and decided to play with some integers. She started with the positive integer $N$. She then noticed that $N$ was too small and boring. Suddenly, she got the idea to create a really big integer. To do so, she multiplied all of the positive divisors of $N$ and got the integer $M$. After getting the value of $M$, she challenged her friend Cisco to determine the value of the original integer $N$ given $M$. Help Cisco find the value of $N$. The input contains one line containing the integer $M$. It is guaranteed that $M$ is a positive integer less than $10^(15)$. Output the original integer $N$ if possible. Otherwise, output $-1$. In the first test case, the positive divisors of 4 are 1, 2, and 4. The product is 8. In the second test case, there is no integer whose product of its positive divisors is 4. ## Input The input contains one line containing the integer $M$. It is guaranteed that $M$ is a positive integer less than $10^(15)$. ## Output Output the original integer $N$ if possible. Otherwise, output $-1$. [samples] ## Note In the first test case, the positive divisors of 4 are 1, 2, and 4. The product is 8. In the second test case, there is no integer whose product of its positive divisors is 4.

**Definitions** Let $ M \in \mathbb{Z}^+ $ be the given product of all positive divisors of some positive integer $ N $. **Constraints** $ 1 \leq M < 10^{15} $ **Objective** Find $ N \in \mathbb{Z}^+ $ such that the product of all positive divisors of $ N $ equals $ M $, i.e., $$ \prod_{d \mid N} d = M $$ If no such $ N $ exists, output $ -1 $. **Key Identity** If $ N $ has $ d(N) $ positive divisors, then: $$ \prod_{d \mid N} d = N^{d(N)/2} $$ Thus, we require: $$ N^{d(N)/2} = M $$

API Response (JSON)

{
  "problem": {
    "name": "H. Riana and Humongous Numbers",
    "description": {
      "content": "Riana got really bored one day and decided to play with some integers. She started with the positive integer $N$. She then noticed that $N$ was too small and boring. Suddenly, she got the idea to crea",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10255H"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Riana got really bored one day and decided to play with some integers. She started with the positive integer $N$. She then noticed that $N$ was too small and boring. Suddenly, she got the idea to crea...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ M \\in \\mathbb{Z}^+ $ be the given product of all positive divisors of some positive integer $ N $.  \n\n**Constraints**  \n$ 1 \\leq M < 10^{15} $\n\n**Objective**  \nFind $ N \\in \\ma...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments