【POJ2773Happy2006题解--数论好题】亦余心之所善兮，虽九死其犹未悔。这篇文章主要讲述POJ2773Happy2006题解--数论好题相关的知识，希望能为你提供帮助。
题目链接
https://cn.vjudge.net/problem/POJ-2773
题意:
求第(k)个与(m)互质的数
分析
因为(gcd(a,b)=gcd(a+t * b,b))
所以在([1,m-1])中与(m)互质的个数与在([kimes m+1,(k+1)imes m-1])的互质(把上一个式子的(b)看成(m)一下就明白了)的个数都等于(phi (m))
然后直接暴力计算出([1,m-1])与其互质的数,再根据周期搞一搞就好了
还有二分+容斥的方法,先挖个坑
代码
#include <
cstdio>
#include <
cstdlib>
#include <
cstring>
#include <
algorithm>
#include <
cctype>
#include <
iostream>
#define ll long long
#define ri register int
using std::min;
using std::max;
template <
class T>
inline void read(T &
x){
x=0;
int ne=0;
char c;
while(!isdigit(c=getchar()))ne=c==‘-‘;
x=c-48;
while(isdigit(c=getchar()))x=(x<
<
3)+(x<
<
1)+c-48;
x=ne?-x:x;
return ;
}
const int maxn=1000005;
const int inf=0x7fffffff;
int num[maxn];
int m,k,tot=0;
int gcd(int a,int b){return b?gcd(b,a%b):a;
}
int main(){
while(scanf("%d %d",&
m,&
k)!=EOF){
tot=0;
for(ri i=1;
i<
=m;
i++){if(gcd(m,i)==1)num[++tot]=i;
}
if(!(k%tot)){printf("%lld
",1ll*(k/tot-1)*m+num[tot]);
}//特判一下
else printf("%lld
",1ll*(k/tot)*m+num[k%tot]);
}
return 0;
}推荐阅读
- audio与video控件/标签的隐藏，iso/Android下自动全屏播放，短暂黑屏问题
- 基于Android平台的图书管理系统的制作
- netAPP存储恢复删除数据方法-留着万一有用呢
- android开发环境搭建
- DK:安卓车牌识别/Android车牌识别SDK/Android车牌识别软件
- 腾讯开源的Android UI框架——QMUI Android
- android EventBus的简单使用
- MVP实战心得—封装Retrofit2.0+RxAndroid+RxBus
- androidEventBus的简单使用