题目
给定r，n求[1，r]内与n互素的个数有多少个？
解题思路
正面想太过复杂，所以从反面来求，那么问题就变成[1,r]中有多少个和n不互质的的数。而要解决这个问题就可以把n的质数都枚举出来，在通过这些质数倍数个数和，减去重叠部分（容斥定理）就可以了。而我写这篇博客的目的是下面代码对位运算的应用让我吃惊。。。祭奠这次发现新大陆。正
阅读背景：
给定r，n求[1，r]内与n互素的个数有多少个？（容斥定理+位运算）_绝丶爵的博客
来源：互联网
分享到：
