O - GCD - Extreme (II)————欧拉函数+数论基本定理

Love The Way You Lie 2024-04-18 15:08 76阅读 0赞

##### 题目要求： #####

[链接][Link 1]  
![在这里插入图片描述][20190908174415651.png]  
题目 给你一个N， 让你求如图这个G。  
其实可以看成![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzODI0Nzkx_size_16_color_FFFFFF_t_70]该题利用唯一分解定理，判断一个**数j** 和**小于j的数** gcd 为 i 的个数

可以百度唯一分解定理（即数论基本定理）

#include<iostream>
    #include<map>
    #include<cstdio>
    #include<cstring>
    #define ll long long
    using namespace std;
    const int maxn = 4e6+5;
    ll phi[maxn];// 存欧拉函数
    ll pre[maxn];// pre[i] 存数i 与小于i个 的gcd和
    ll ans[maxn];// 存答案
    ll cnt = 0;
    void e_Prime()// 打表求欧拉函数
    { 
    
        memset(phi, 0, sizeof(phi));
        for(ll i = 2;i < maxn;i++)
        { 
            if(!phi[i])
            { 
                 cnt++;
                for(ll j = i;j <maxn;j+=i)
                { 
                    if(!phi[j])phi[j] = j;
    
                    phi[j] = phi[j]*(i-1)/i;
                }
            }
        }
    
    }
    void init()
    { 
        memset(ans, 0, sizeof(ans));
        memset(pre,0,sizeof(pre));
    }
    int main()
    { 
        ios_base::sync_with_stdio(false);
        e_Prime();
        init();
        for(ll i = 1;i < maxn;i++)// 求pre[i]
        { 
            for(ll j = 2*i;j < maxn;j+=i)
            { 
                pre[j] += i*phi[j/i]; //这里涉及一些唯一分解定理
            }
        }
        for(ll i = 1;i < maxn;i++)// 打表求答案
            ans[i] = ans[i-1]+pre[i];
    
        ll n;
        while(cin>>n&&n)
        { 
            cout<<ans[n]<<endl;
        }
    
    
        return 0;
    }

[Link 1]: https://vjudge.net/problem/UVA-11426
[20190908174415651.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/d6eb9573a28f408eb8454b3ff92845cf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzODI0Nzkx_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/939cc67c80dc4c54b7ad80da316d34a7.png