nyoj 762:第k个互质数
2024-10-07 09:42:10
题目链接:http://acm.nyist.net/JudgeOnline/problem.php?pid=762
直接给代码好了,容斥原理具体看《组合数学》
#include<bits/stdc++.h> using namespace std; typedef long long LL; vector<int> a; //存储n所有质因子 //不爆int情况下,大概最多10个左右 ]; void getfac(int x) { ;i*i<=x;i++) ) { a.push_back(i); ) x/=i; } ) a.push_back(x); } int cal(int x) //由容斥原理计算1~x中有多少与n互质的自然数 { ,ret=x; b[++g]=; //由以下的二重for循环可以做到枚举组合,共2^(a.size())个组合 ;i<a.size();i++) { int t=g; ;j<=g;j++) b[++t]=-b[j]*a[i],ret+=x/b[t]; g=t; } return ret; } int work(int n,int k) //二分查找 { ,r=2e9; //cal(l)<k,cal(r)>=k ) //当r-l=1时,结束循环,此时cal(r)=k { ; if(cal(mid)<k) l=mid; else r=mid; } return r; } int main() { int n,k; while(cin>>n>>k) { a.clear(); getfac(n); printf("%d\n",work(n,k)); } }
最新文章
- [AHOI 2009] 维护序列(线段树模板题)
- Web前端入门必学知识
- linux注销、关机、重启
- 24Mybatis_延迟加载——用association来实现
- Tomcate配置单向双向SSL
- iomanip,setw(),setw: undeclared identifier
- jQuery、实例大全
- Function.prototype.call.apply结合用法
- Hibernate 关联关系映射实例
- wemall app商城源码Android之ListView异步加载网络图片(优化缓存机制)
- RabbitMQ --- Publish/Subscribe(发布/订阅)
- 【转载】SSH协议及其应用
- 饿了么vue-cli3.0+cube-ui笔记
- ABP框架系列之二十:(Dependency-Injection-依赖注入)
- Gtk-WARNING**:无法在模块路径中找到主题引擎:“pixmap”的解决
- mybatis基于注解形式的多数据源
- ASP入门(十四)-FileSystemObject 对象
- &;lt;图形图像,动画,多媒体&;gt; 读书笔记 --- 音效
- 每日英语:China Destroys Six Tons of Confiscated Ivory
- 理解 RESTful 架构(转)