#P4729. 舞!舞!舞!

    ID: 3850 传统题 1000ms 256MiB 尝试: 12 已通过: 3 难度: 9 上传者: 标签>难度分类省选/NOI-排序与序列处理二分第 k 小数论莫比乌斯反演杜教筛整除分块线性筛欧拉函数Miller–Rabin枚举与搜索回溯搜索约数个数乘积公式最佳优先搜索状态去重模拟与实现技巧高精度乘法CF2800

舞!舞!舞!

题目背景

"如何是好呢,我?"我重复刚才的问话。 "刚才我已说了,尽力而为就是,争取把你连接妥当。"羊男说,"但只这样还不够,你自己也必须全力以赴,不能光是静坐空想,那样你永远走投无路,明白吗?" "明白。"我说,"那么我到底如何是好呢?" "跳舞,"羊男说,"只要音乐在响,就尽管跳下去。明白我的话?跳舞!不停地跳舞!不要考虑为什么跳,不要考虑意义不意义,意义那玩艺儿本来就没有的。"

题目描述

给定一个函数 ff、它的目标值 vv 和正整数 KK。将所有满足 f(N)=vf(N)=v 的正整数 NN 按从小到大的顺序排列,求其中第 KK 个。

可选的函数如下。

类型 函数 定义
11 莫比乌斯函数 μ(N)\mu(N) μ(1)=1\mu(1)=1。若存在素数 pp 使 p2∣Np^2\mid N,则 μ(N)=0\mu(N)=0。否则若 NN 有 rr 个不同的素因子,则 μ(N)=(−1)r\mu(N)=(-1)^r
22 欧拉函数 φ(N)\varphi(N) 满足 1≤i≤N1\le i\le N 且与 NN 互质的整数 ii 的个数
33 约数个数函数 d(N)d(N) NN 的正约数个数

输入格式

一行包含三个整数 type,v,K\mathrm{type},v,K,分别表示函数类型、目标值和排名。每份输入只包含一次查询。

输出格式

输出一行一个整数,表示满足条件的第 KK 小的正整数 NN。

数据范围

保证输入合法,所求的第 KK 个数存在。

类型 范围
11 v∈{−1,0,1}v\in\{-1,0,1\},1≤K≤1081\le K\le10^8
22 1≤v≤10101\le v\le10^{10},1≤K≤10001\le K\le1000,答案不超过 101210^{12}
33 1≤v≤1071\le v\le10^7,1≤K≤501\le K\le50,答案不超过 1010010^{100}

样例 #1

样例输入 #1

1 1 1

样例输出 #1

1

样例 #2

样例输入 #2

2 1 1

样例输出 #2

1

样例 #3

样例输入 #3

3 1 1

样例输出 #3

1

样例 #4

样例输入 #4

1 1 70926127

样例输出 #4

233333333

样例 #5

样例输入 #5

2 219104256 14

样例输出 #5

233333333

样例 #6

样例输入 #6

3 123 4

样例输出 #6

133040906960896