POJ - 2407 - Relatives（欧拉函数 + 约数个数定理）

青旅半醒 2022-06-08 11:21 198阅读 0赞

求出比n小，且与n互素数的个数；

模板题，对于一个大于1正整数n可以分解质因数：

![这里写图片描述][a8ec8a13632762d0a5814266a7ec08fa503dc6a8.jpg]

则n的正约数的个数就是

![这里写图片描述][8ad4b31c8701a18b94aed93e9d2f07082838fe7e.jpg]

其中a1、a2、a3…ak是p1、p2、p3，…pk的指数。  
化简后：

![这里写图片描述][1008672-20170503125207086-2060438470.png]

然后用程序表达后就是：

int phi[MAXN];
    
    int euler_phi(int n) {
        int m = (int)sqrt(n + 0.5);//防止数据偏小
        int ans = n;
        for(int i = 2; i <= m; i++) if(n % i == 0) {
            ans = ans / i * (i - 1);//吧上面的公式化简一下就得到了
            while(n % i == 0) n /= i;
        } 
        if(n > 1) ans = ans / n * (n - 1);
        return ans;
    }

没什么好说的，理解吧

AC代码：

#include<iostream>
    #include<cmath>
    #define ll long long
    
    using namespace std;
    
    ll euler(ll n) {
        ll m = (ll)sqrt(n + 0.5);
        ll ans = n;
        for(ll i = 2; i <= m; i++) {
            if(n%i == 0) {
                ans = ans / i * (i - 1);
                while(n % i == 0) n /= i; 
            }
        }   
        if(n > 1) ans = ans / n * (n - 1);
        return ans;
    }
    
    int main() {
        ll n;
        while(scanf("%lld", &n) && n) {
            printf("%d\n", euler(n));
        }
        return 0;
    }

[a8ec8a13632762d0a5814266a7ec08fa503dc6a8.jpg]: https://gss2.bdstatic.com/9fo3dSag_xI4khGkpoWK1HF6hhy/baike/s=231/sign=e19b382db04543a9f11bfdcf2f168a7b/a8ec8a13632762d0a5814266a7ec08fa503dc6a8.jpg
[8ad4b31c8701a18b94aed93e9d2f07082838fe7e.jpg]: https://gss3.bdstatic.com/-Po3dSag_xI4khGkpoWK1HF6hhy/baike/s=316/sign=ca4b36d4d243ad4ba22e40c1b4035a89/8ad4b31c8701a18b94aed93e9d2f07082838fe7e.jpg
[1008672-20170503125207086-2060438470.png]: /images/20220608/43cd468719d5464289a9fbb06284194c.png