#P3568. DZY Loves Math VII

    ID: 2766 传统题 1000ms 512MiB 尝试: 289 已通过: 11 难度: 10 上传者: 标签>难度分类省选/NOI-排序与序列处理二分第 k 小数论线性筛杜教筛整除分块Miller–Rabin枚举与搜索深度优先搜索最优性剪枝约数个数乘积公式最佳优先搜索状态去重模拟与实现技巧高精度乘法高精度除法CF2900

DZY Loves Math VII

DZY Loves Math VII

题目描述

设 μ(N)\mu(N) 是莫比乌斯函数,φ(N)\varphi(N) 是欧拉函数,d(N)d(N) 是 NN 的正因数个数。对每个函数分别给出一个函数值和一个名次 KK,求使该函数取给定值的、按从小到大排列的第 KK 个正整数 NN。

其中 μ(1)=1\mu(1)=1。若 NN 含有某个质数的平方因子,则 μ(N)=0\mu(N)=0;否则,若 NN 恰有 ss 个不同的质因子,则 μ(N)=(−1)s\mu(N)=(-1)^s。

输入格式

输入三行,每行两个整数 v,Kv,K。三行依次给出 μ(N)=v\mu(N)=v、φ(N)=v\varphi(N)=v、d(N)=vd(N)=v 的查询。KK 为正整数;第一行的 vv 可以是 −1-1、00 或 11。

输出格式

输出三行,每行一个正整数,依次表示三组查询的答案。

样例 #1

1 1
1 1
1 1
1
1
1

样例 #2

1 70926127
219104256 14
123 4
233333333
233333333
133040906960896

数据范围

查询 函数值范围 名次上限 答案上限
μ\mu ∣v∣≤1\lvert v\rvert\le1 10810^8 未另设上限
φ\varphi 1≤v≤10101\le v\le10^{10} 10001000 101210^{12}
dd 1≤v≤1071\le v\le10^7 5050 1010010^{100}

共有五组评测数据。所有查询保证有合法答案。