ID: ZL22602

传统题

2000ms

128MiB

普及−

上传者:

标签>

M2

M2第二学期

M2-第26课

唯一分解、互质与最简分数

没有共同零件的搭档

互质

算法相关

算法-有限枚举

算法-欧几里得算法

作业题

第K个互质朋友

题目描述

把所有与 n 互质的正整数按从小到大排列，并从1开始编号，求第 k 个。

输入格式

一行输入 n、k，满足 1≤n,k≤10^5。

输出格式

输出第 k 个满足 gcd(x,n)=1 的正整数 x。

样例

输入

1 1

输出