#P3643. Phi的反函数

    ID: 2837 传统题 1000ms 64MiB 尝试: 526 已通过: 232 难度: 6 上传者: 标签>难度分类提高数论欧拉函数约数成对枚举试除法判素数枚举与搜索回溯搜索可行性剪枝最优性剪枝CF1900ByZky

Phi的反函数

Phi 的反函数

题目描述

给定正整数 nn,求满足 φ(x)=n\varphi(x)=n 的最小正整数 xx。欧拉函数 φ(x)\varphi(x) 表示 11 至 xx 中与 xx 互质的整数的个数,特别地,φ(1)=1\varphi(1)=1。

输入格式

输入一个正整数 nn,其中 1≤n<2311\le n<2^{31}。

输出格式

如果不存在这样的 xx,或最小的 xx 大于 2312^{31},输出 −1-1。否则输出最小的 xx。

4
5