Project Euler 448

题目

Average least common multiple

The function \(\mathbf{lcm}(a,b)\) denotes the least common multiple of \(a\) and \(b\).

Let \(A(n)\) be the average of the values of \(\mathbf{lcm}(n,i)\) for \(1\le i\le n\).

E.g: \(A(2)=(2+2)/2=2\) and \(A(10)=(10+10+30+20+10+30+70+40+90+10)/10=32\).

Let \(S(n)=\sum A(k)\) for \(1\le k\le n\).

\(S(100)=122726\).

Find \(S(99999999019) \bmod 999999017\).

解决方案

化简\(A(n)\)，有

\(\begin{aligned} A(n)&=\sum_{i=1}^n \dfrac{\mathbf{lcm}(n,i)}{n}\\ &=\sum_{i=1}^n \dfrac{i}{\gcd(n,i)}\\ &=\sum_{g\mid n}\sum_{m=1}^{n/g} [\gcd(n/g,m)=1]\cdot m\\ &=\sum_{d\mid n}\sum_{m=1}^{d} [\gcd(d,m)=1]\cdot m\\ \end{aligned}\)

令\(\displaystyle{f(n)=\sum_{m=1}^{n} [\gcd(n,m)=1]\cdot n}\)，根据OEIS序列A023896，可以知道:

\(f(n)= \left \{\begin{aligned} &1 & & \text{if}\quad n=1 \\ &\dfrac{n\cdot \varphi(n)}{2}& & \text{else} \end{aligned}\right.\)

那么可以如下化简\(S(n)\)：

\(\begin{aligned} S(n)&=\sum_{m=1}^n A(m)\\ &=\sum_{m=1}^n \sum_{d\mid m} f(n)\\ &=\sum_{m=1}^n \left\lfloor\dfrac{n}{m}\right\rfloor\cdot f(n)\\ &=n+\dfrac{1}{2}\sum_{m=2}^n \left\lfloor\dfrac{n}{m}\right\rfloor\cdot m\cdot \varphi(m)\\ &=\dfrac{1}{2}\left(n+\sum_{m=1}^n \left\lfloor\dfrac{n}{m}\right\rfloor\cdot m\cdot \varphi(m)\right)\\ \end{aligned}\)

那么接下来的任务是计算\(\displaystyle{g(n)=\sum_{m=1}^n \left\lfloor\dfrac{n}{m}\right\rfloor\cdot m\cdot \varphi(m)}\)的值。

令\(\displaystyle{h(n)=\sum_{m=1}^n m\cdot \varphi(m)}\)。不难发现，我们可以使用数论分块来计算\(g(n)\)的值：

\[g(n)=\sum_{n=1}^{\lfloor\frac{n}{t+1}\rfloor} \left\lfloor\dfrac{n}{m}\right\rfloor\cdot m\cdot \varphi(m) + \sum_{m=1}^t m\cdot\left(h\left(\left\lfloor\dfrac{n}{m}\right\rfloor\right)-h\left(\left\lfloor\dfrac{n}{m+1}\right\rfloor\right)\right)\]

其中\(t=\lfloor\sqrt{n}\rfloor\)。

那么接下来就是计算\(h(n)\)的值，有：

\(\begin{aligned} \dfrac{n(n+1)(2n+1)}{6} &=\sum_{k=1}^n k^2\\ &=\sum_{k=1}^n k\cdot \sum_{d\mid k}\varphi(d)\\ &=\sum_{d=1}^n \varphi(d)\cdot \sum_{i=1}^{\lfloor n/d\rfloor}(id)\\ &=\sum_{d=1}^n \varphi(d)\cdot d\cdot \sum_{i=1}^{\lfloor n/d\rfloor}i\\ &=\sum_{i,d\ge 1;id\le n}^n \varphi(d)\cdot d\cdot i\\ &=\sum_{i=1}^n i\cdot \sum_{d=1}^{\lfloor n/i\rfloor} \varphi(d)\cdot d\\ &=\sum_{i=1}^n i\cdot h\left(\left\lfloor\dfrac{n}{i}\right\rfloor\right) \end{aligned}\)

因此，可以得到关于\(h\)的递归式：

\[h(n)=\dfrac{n(n+1)(2n+1)}{6}-\sum_{i=2}^n i\cdot h\left(\left\lfloor\dfrac{n}{i}\right\rfloor\right)\]

因此，同样右边这一部分可以继续使用数论分块来解决。

代码

#include <bits/stdc++.h>
#include "tools.h"
using namespace std;
typedef long long ll;

const ll N=99999999019;

ll mod=999999017;
ll inv6=mod_inverse(6,mod);
ll inv2=mod_inverse(2,mod);
unordered_map<ll,ll>mp;
const int M=20000000;
int phi[M+4];
ll sg[M+4];
ll s(ll n){
    n%=mod;
    return n*(n+1)%mod*(n*2+1)%mod*inv6%mod;
}
ll calH(ll n){
    if(n<=M) return sg[n];
    else if(mp.count(n)) return mp[n];
    ll ans=s(n);
    for(ll l=2,r;l<=n;l=r+1){
        r=n/(n/l);
        ans-=(l+r)%mod*((r-l+1)%mod)%mod*inv2%mod*calH(n/l)%mod;
    }
    ans=(ans%mod+mod)%mod;
    return mp[n]=ans;
}
ll cal(){
    ll ans=0;
    for(int i=1;i<=min(N,1ll*M);i++)
        ans=(ans+N/i%mod*phi[i]%mod*i)%mod;
    for(ll l=M+1,r;l<=N;l=r+1){
        ll k=N/l;r=N/k;
        ans=(ans+k*(calH(r)-calH(l-1)+mod)%mod)%mod;
    }
    return (ans+N)%mod*inv2%mod;
}
int main(){
    for(int i=1;i<=M;i++)
        phi[i]=i;
    for(int i=2;i<=M;i++)
        if(phi[i]==i){
            for(int j=i;j<=M;j+=i)
                phi[j]=phi[j]/i*(i-1);
        }
    for(int i=1;i<=M;i++)
        sg[i]=(sg[i-1]+1ll*i*phi[i])%mod;
    ll ans=cal();
    printf("%lld\n",ans);
}