POJ2773Happy2006题解--数论好题 _数论

【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; }

POJ2773Happy2006题解--数论好题

推荐阅读

什么是职场？

百日练，一百天读一百本书，打卡第9天，《你只是看上去很努力》35分钟，理解50%，2000/分钟

空调主机跟遥控器显示温度不同步是怎么回事新科柜机空调不制冷调节温度显示不同步

等闲识得东风面中的东风是什么意思等闲识得东风面释义

redis 集合的底层实现 redis集合存bean

Java中关于Collections集合工具类的详细介绍

福州贵安水世界好玩吗 2023福州贵安水世界门票多少钱一张

蜗居背景音乐歌词蜗居背景音乐歌词翻译

甘肃所有大学名单甘肃省大学排名

雷殿生名字打分99分雷王姓取名

python|python 的生产者和消费者模式

quiet怎么读 quiet怎么造句

龙眼肉罐头做法新鲜的龙眼肉怎么做罐头

海藻面膜敷多长时间好

mysql my.cnf配置模板参考

苹果扣费怎么退 iPhone扣费怎么退款

你认为孤独的根源是什么？

减肥期间,有哪些做起来简单又好吃的减肥食谱？

创维55寸4k智能电视多少钱一台哪个电视牌子好

二甲双胍|糖尿病天天吃二甲双胍，请花5分钟弄清这6个注意事项，很重要