「QFOI R2」树色尤含残雨

Luogu

IDLGP10411

Time1000ms

Memory512MB

DifficultyP3

数学贪心数论洛谷原创O2优化洛谷月赛

小 R 是一个可爱的女孩子，她喜欢分解质因数。她有一个正整数 $x$。每次操作可以选择 $p_1,\alpha_1,p_2,\alpha_2$ 满足 $p_1,p_2$ 为两不同质数且 $\alpha_1,\alpha_2$ 为正整数，若 $x$ 是 $p_1^{\alpha_1}p_2^{\alpha_2}$ 的整数倍，就将 $x$ 除以 $p_1^{\alpha_1}p_2^{\alpha_2}$，否则操作无效。请你求出通过若干次操作可以得到的最小的 $x$。 ## Input 一行一个整数 $x$。 ## Output 一个整数，表示可以得到的最小的 $x$。 [samples] ## Note **样例 $1$ 解释** 无法进行任何有效操作。 --- **样例 $2$ 解释** 可以进行以下两次操作： - 令 $p_1=2,\alpha_1=1,p_2=3,\alpha_2=1$，将 $x$ 除以 $p_1^{\alpha_1}p_2^{\alpha_2}=2^13^1=6$，得到 $x=20$。 - 令 $p_1=2,\alpha_1=2,p_2=5,\alpha_2=1$，将 $x$ 除以 $p_1^{\alpha_1}p_2^{\alpha_2}=2^25^1=20$，得到 $x=1$。 --- **数据范围** **本题采用捆绑测试。只有通过子任务中所有测试点以及所有依赖的子任务，才能获得相应的分数。** 对于全部数据：$2\le x\le 10^9$。 - 子任务一（$10$ 分）：$x\le 10$。 - 子任务二（$20$ 分）：$x$ 为“无平方因子数”$^\dagger$。 - 子任务三（$20$ 分）：$x$ 为一个质数的正整数次幂。 - 子任务四（$20$ 分）：$x\le 10^5$。依赖子任务一。 - 子任务五（$30$ 分）：无特殊限制。依赖子任务一、二、三、四。 $\dagger$ 称一个数 $x$ 为“无平方因子数”，当且仅当不存在大于一的整数 $k$，使得 $x$ 是 $k^2$ 的整数倍。

Samples

Input #1

Output #1

Input #2

Output #2

Input #3

Output #3

API Response (JSON)

{
  "problem": {
    "name": "「QFOI R2」树色尤含残雨",
    "description": {
      "content": "小 R 是一个可爱的女孩子，她喜欢分解质因数。 她有一个正整数 $x$。每次操作可以选择 $p_1,\\alpha_1,p_2,\\alpha_2$ 满足 $p_1,p_2$ 为两不同质数且 $\\alpha_1,\\alpha_2$ 为正整数，若 $x$ 是 $p_1^{\\alpha_1}p_2^{\\alpha_2}$ 的整数倍，就将 $x$ 除以 $p_1^{\\alpha_1}p_2^{\\alpha",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10411"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "小 R 是一个可爱的女孩子，她喜欢分解质因数。\n\n她有一个正整数 $x$。每次操作可以选择 $p_1,\\alpha_1,p_2,\\alpha_2$ 满足 $p_1,p_2$ 为两不同质数且 $\\alpha_1,\\alpha_2$ 为正整数，若 $x$ 是 $p_1^{\\alpha_1}p_2^{\\alpha_2}$ 的整数倍，就将 $x$ 除以 $p_1^{\\alpha_1}p_2^{\\alpha...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments