P1592 互质

题目描述

输入两个正整数 $n$ 和 $k$，求与 $n$ 互质的第 $k$ 个正整数。

输入格式

仅一行，为两个正整数 $n$ 和 $k$。

输出格式

一个正整数，表示与 $n$ 互质的第 $k$ 个正整数。

输入输出样例 #1

输入 #1

10 5

输出 #1

11

说明/提示

数据规模与约定

对于所有的数据，保证 $1\le n\le 10^6$，$1\le k\le 10^8$。

C++实现

#include
#include
#include
#include
#include
using namespace std;

const int N=1e6+5;

int n,k;
int a[N],cnt;
int main()
{
scanf(“%d%d”,&n,&k);
for(int i=1;i<n;++i)
if(__gcd(i,n)==1)
a[++cnt]=i;
printf(“%d”,(k-1)/cnt*n+a[(k-1)%cnt+1]);
return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容