洛谷题解 P1592 【互质】
2024-09-06 18:46:06
原题传送门
题目描述
输入两个正整数n和k,求与n互质的第k个正整数。
输入格式
仅一行,为两个正整数n(≤10^6)和k(≤10^8)。
输出格式
一个正整数,表示与n互质的第k个正整数。
输入输出样例
输入 #1
10 5
输出 #1
11
--------------------------------------------------以下为题解部分---------------------------------------
分析:
思路:
这个题通读一遍题以后,你会发觉:这不就是一道纯数学题吗?
既然看懂了题意,那就很简单了。
补充一点简单的数论知识:
两个数的最大公因数是1是,此两数互质。(dalao勿喷)
好了,不多说,上代码
代码:
#include<cstdio>
using namespace std;
int n,k,q,p[1000010];
inline int gcd(int a,int b){ //计算a,b的最大公因数
return b==0?a:gcd(b,a%b);
}
int main(){
scanf("%d %d",&n,&k);
for(int i=1;i<=n;i++){ //枚举
if(gcd(n,i)==1) //众所周知,当两个数的最大公因数为1时,此两数互质。
p[++q]=i; //记录结果
}
printf("%d",(k-1)/q*n+p[k%q]); //输出n互质的第k个正整数。
return 0;
}
最新文章
- .net(C#)中this关键字
- Request.ServerVariables 获取服务器或者客户端信息
- java分割字符串
- Excel里生成GUID
- PHP中CURL方法curl_setopt()函数的参数
- 网络爬虫讲解(附java实现的实例)
- 【BZOJ-4692】Beautiful Spacing 二分答案 + 乱搞(DP?)
- zookeeper源码分析(一) 工作原理
- [vB.NET]为控件添加鼠标悬浮时的提示气泡
- Flash Builder中“Error: #2036 加载未完成”错误的解决方法
- js判断输入框的范围,并且只能输入数字
- 请求(Request)的参数(Parameter)里包含特殊字符(#等)的正确处理方式
- Java中的工具类和新特性
- MYSQL 数据库高频查询语句整理
- phpwind9.0升级到php7后出现的问题修复
- transform,transtion属性
- 货币转换 I
- java基础回忆、复习(一)
- SQL给数据编号
- 算法训练 P0505