poj2773如何运用二分和容斥原理求解欧拉函数？

本文共计1297个文字，预计阅读时间需要6分钟。

欧几里得定理告诉我们gcd(n, m)=gcd(n, n-m)，那么就有gcd(n, m)=gcd(n, n+m)。因此，对于n个数的gcd取值情况，实际上与n个数的gcd取值情况是相同的。

然后，可以利用欧拉函数的性质将问题转化为在n内的某个问题。之后，可以进一步利用欧拉函数的性质将问题转化为在n内的某个问题。

最后，可以得出结论：gcd(n, m)=gcd(n, n+m)=gcd(n, n-m)。

欧几里得定理告诉我们gcd(n,m)==gcd(n,n-m)，那么就有gcd(n,m)==gcd(n,n+m)

因此，对每n个数，与n取gcd的情况其实是相同的。。

然后可以利用欧拉函数把m的问题转化为在n内的问题。。

然后剩下的就是如何在1..n找第m个和n互斥的数了。。

直接枚举貌似可以过。。然而这样还要预处理欧拉函数干嘛。。所以肯定有更快的做法。。

找数肯定用二分查找比较优秀，关键是如何check。。

最主要还是找出1..t内有多少数和n互斥，其实对n分解质因数后就可以用容斥做了。。