Relatives FZU1012————（算术基本定理+容斥）

àì夳堔傛蜴生んèń 2022-05-18 00:10 159阅读 0赞

Given n, a positive integer, how many positive integers less than n are relatively prime to n? Two integers a and b are relatively prime if there are no integers x > 1, y > 0, z > 0 such that a = xy and b = xz.  
**Input**  
There are several test cases. For each test case, standard input contains a line with n <= 1,000,000,000. A line containing 0 follows the last case.  
Output  
For each test case there should be single line of output answering the question posed above.  
**Sample Input**  
7  
12  
0  
**Sample Output**  
6  
4

--------------------

找出1⋯n−1  1 ⋯ n − 1 种与n互质的数的个数  
可以用欧拉函数解决或者用容斥定理

--------------------

欧拉函数：

//#include<bits/stdc++.h>
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<string>
    #include<algorithm>
    #include<map> 
    
    
    using namespace std;
    typedef long long ll;
    
    
    map<ll ,ll > p(ll n)
    {
        map<ll,ll> ans;
        for(ll i=2;i*i<=n;i++)
        {
            while(n%i==0)
            {
                ans[i]++;
                n/=i;
            }
        }
        if(n!=1)    ans[n]++;
        return ans;
    }
    
    
    int main()
    {
        int n;
        while(~scanf("%d",&n)&&n)
        {
            map<ll,ll> ans=p(n); 
            ll ans1=n;
            for(map<ll,ll>::iterator ite=ans.begin();ite!=ans.end();ite++)
            {
                ans1=ans1*(ite->first-1)/ite->first;
            }
            printf("%lld\n",ans1);      
         } 
        return 0;
    }

用容斥定理写一下

--------------------

#include <cstdio>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    typedef long long ll;
    ll gcd(ll a,ll b)
    {
        return !b?a:gcd(b,a%b);
    }
    ll lcm(ll a,ll b)
    {
        return a/gcd(a,b)*b;
    }
    
    int k;
    ll p[50000];
    void getprime(ll n)
    {
        k=0;
        for(ll i=2;i*i<=n;i++)
        {
            while(n%i==0)
            {
                p[k++]=i;
                n/=i;
            }
    
        }
        if(n!=1)    p[k++]=n;
    }
    
    int main()
    {
        ll n;
        while(~scanf("%lld",&n)&&n)
        {
            ll b=n;
            ll ans=0;
            getprime(n);
            for(int i=1;i<(1<<k);i++)
            {
                ll cnt=0;
                ll temp=1;
                for(int j=0;j<k;j++)
                    if(i>>j & 1)
                    {
                        temp=lcm(temp,p[j]);
                        cnt++;
                    }
                if(cnt&1)   ans+=(b-1)/temp;
                else        ans-=(b-1)/temp;
            }
            printf("%lld\n",b-1-ans);
        }
        return 0;
    }