luogu1891 疯狂lcm

灰太狼 2021-11-01 23:24 245阅读 0赞

### 题目描述 ###

描述：

众所周知，czmppppp是数学大神犇。一天，他给众蒟蒻们出了一道数论题，蒟蒻们都惊呆了。。。

给定正整数N，求LCM(1,N)+LCM(2,N)+...+LCM(N,N)。

### 输入格式 ###

第一行一个数T，表示有T组数据。

对于每组数据，一行，一个正整数N。

### 输出格式 ###

T行，每行为对应答案。

### 输入输出样例 ###

输入 \#1复制

3
    1
    2
    5

输出 \#1复制

1
    4
    55

### 说明/提示 ###

对于30%的数据，1≤T≤5，1≤N≤100000

对于100%的数据，1≤T≤300000，1≤N≤1000000

看见$lcm$一般要转成$gcd$

$\\sum\_\{i=1\}^\{N\}\{lcm(i,N)\}\\\\\\\\=\\sum\_\{i=1\}^\{N\}\{\\frac\{i\*N\}\{gcd(i,N)\}\}\\\\\\\\=\\sum\_\{d|N\}^\{N\}\{\\frac\{1\}\{d\}\*\\sum\_\{d|i\}^\{N\}\{\[gcd(i,j)==1\]\*i\*N\}\}\\\\\\\\=\\sum\_\{d|N\}^\{N\}\{\\sum\_\{i=1\}^\{\\frac\{N\}\{d\}\}\{\[gcd(\\frac\{N\}\{d\},i)==1\]\*i\*N\}\}\\\\\\\\=N\*\\sum\_\{d|N\}^\{N\}\{\\sum\_\{i=1\}^\{\\frac\{N\}\{d\}\}\{\[gcd(\\frac\{N\}\{d\},i)==1\]\*i\}\}\\\\\\\\=N\*\\sum\_\{d|N\}^\{N\}\\frac\{d\*\\phi(d)+\[d==1\]\}\{2\}$

最后一步是根据欧拉反演得出的

欧拉反演主要有两种形式

$\\sum\_\{d|N\}^\{N\}\{\\phi(d)\}=N\\\\\\\\\\sum\_\{i=1\}^\{N\}\{\[gcd(i,N)==1\]\*i\}=\\frac\{\[N==1\]+\\phi(N)\*N\}\{2\}$

这里使用的是后一种

#include<bits/stdc++.h>
    using namespace std;
    const int N=1e6+5;
    int n;
    int phi[N],pre[N];
    int prime[N],cnt;
    bool isprime[N];
    void calc_phi()
    {
        phi[1]=1;
        for(int i=2;i<N;++i) isprime[i]=1,pre[i]=1; 
        for(int i=2;i<N;++i)
        {
            if(isprime[i]) prime[++cnt]=i,phi[i]=i-1,pre[i]=i;
            for(int j=1;j<=cnt && 1ll*prime[j]*i<N;++j)
            {
                if(pre[i]<prime[j]) break;
                isprime[i*prime[j]]=0;
                pre[i*prime[j]]=prime[j];
                phi[i*prime[j]]=phi[i]*(i%prime[j]?prime[j]-1:prime[j]);
            }
        }
    }
    int main()
    {
        calc_phi();
        int T;
        scanf("%d",&T);
        while(T--)
        {
            long long ans=0;
            scanf("%d",&n);
            for(int i=1;i*i<=n;++i)
            if(n%i==0)
            {
                ans+=1ll*i*phi[i]+(i==1);
                if(i*i!=n) ans+=1ll*(n/i)*phi[n/i];
            }
            ans=(ans/2)*n;
            printf("%lld\n",ans);
        }
        return 0;
    }

转载于:https://www.cnblogs.com/w19567/p/11273236.html