简单的数学题

\[\Sigma _{i=1}^{n} \Sigma _{j=1}^{n} ijgcd(i,j) \,\,\,\,n\leqslant1e10 \]

正常莫反

\[\Sigma _{d=1}^{n} \Sigma _{i=1}^{\lfloor {\frac{n}{d}} \rfloor} \Sigma _{j=1}^{\lfloor {\frac{n}{d}} \rfloor} ij[gcd(i,j)==1] \]

\[\Sigma _{d=1}^{n} \Sigma _{i=1}^{\lfloor {\frac{n}{d}} \rfloor} \Sigma _{j=1}^{\lfloor {\frac{n}{d}} \rfloor} ij \Sigma _{p|i,p|j} \mu(p) \]

\[\Sigma _{d=1}^{n} \Sigma _{p=1}^{\lfloor {\frac{n}{d}} \rfloor} p^2 \mu(p) (1+2+3+……+{\lfloor {\frac{n}{pd}} \rfloor}) \]

\[令 Sum(n)=(1+2+……+n)\,\,\,\,\,\,T=dp \]

\[\Sigma _{T=1}^{n} Sum(\lfloor {\frac{n}{T}} \rfloor) T^2 \Sigma _{d|T}d\mu(\lfloor {\frac{T}{d}} \rfloor) \]

筛出 $ T^2 \Sigma _{d|T} d\mu(\lfloor {\frac{T}{d}} \rfloor) $

…………sb

发现 $$ id * \mu (i) = \Sigma _{d|i} id(d)\mu(\lfloor {\frac{i}{d}} \rfloor) =\varphi(i) $$
好东西

\[T^2 \Sigma _{d|T} d\mu(\lfloor {\frac{T}{d}} \rfloor) = T^2 \varphi(T) \]

\[f(i)=i^2\varphi(i) \,\,\, S(n)= \Sigma _{i=1}^{n} f(i) \]

\[令 g(x)=x^2 .\,\,\, 则S(n)= \Sigma _ {i=1}^{n} g*f(i) - \Sigma _{i=2}^{n} g(i)S(\lfloor {\frac{n}{i}} \rfloor) \]

\[g*f(i) = \Sigma _{d|i} d^2*{\frac{i^2}{d^2}} \varphi(d) = i^3 \]

\[S(n)=\Sigma _{i=1}^{n} i^3- \Sigma _{i=2}^{n} i^2S(\lfloor {\frac{n}{i}} \rfloor) \]

$ \Sigma _{i=1}^{n} i^3=(\Sigma _{i=1}^{n} i)^2 ,,,, \Sigma _{i=1}^{n} i^2= {\frac{n(n+1)(2*n+1)}{6}} $

\[\Sigma _{T=1}^{n} Sum(\lfloor {\frac{n}{T}} \rfloor ) S(T) \]

模数是随机模数………… 取模要勤


#include<cstdio>
#include<unordered_map>

#define ll long long

using namespace std;
const int N=4e6;

int p[N+5],cnt,flag[N+5];
ll phi[N+5];
ll mod;

ll ksm(ll a,ll b){
    ll ans=1;
    
    while(b){
        if(b&1)
            ans=(ans%mod*a%mod)%mod;
        a=a%mod*a%mod;
        b>>=1;
    }
    return ans;
}

void solve(){
    phi[1]=1;

    for(int i=2;i<=N;i++){
        if(!flag[i]){
            p[++cnt]=i;
            phi[i]=(i-1+mod)%mod;
        }
        for(int j=1;j<=cnt&&i*p[j]<=N;j++){
            int k=i*p[j];
            
            flag[k]=1;

            if(i%p[j]==0){
                phi[k]=phi[i]%mod*p[j]%mod;
                break;
            }
            phi[k]=phi[i]*(p[j]-1+mod)%mod;
        }
    }
    for(int i=1;i<=N;i++){
        phi[i]=(phi[i-1]+i%mod*i%mod*phi[i]%mod)%mod;
    }
}

unordered_map <ll,ll> sum;
ll inv2,inv6;

ll Sum(ll n){
    n%=mod;
    return n%mod*(n+1)%mod*inv2%mod;
}
ll Sum1(ll n){
    n%=mod;
    return n%mod*(n+1)%mod*(2*n+1)%mod*inv6%mod;
}

ll Sumphi(ll n){
    if(n<=N)
        return phi[n];
    if(sum[n])
        return sum[n]%mod;
    
    ll l=2,x=Sum(n)%mod,ans=x%mod*x%mod;
    ans%=mod;

    while(l<=n){
        ll r=n/(n/l);
        ans=(ans-(Sum1(r)-Sum1(l-1)+mod)%mod*Sumphi(n/l)%mod+mod)%mod;
        l=r+1;
    }
    return sum[n]=(ans+mod)%mod;
}

int main(){
    ll n;

    scanf("%lld%lld",&mod,&n);

    solve();
    inv2=ksm(2,mod-2);
    inv6=ksm(6,mod-2);

    ll ans=0,l=1;

    while(l<=n){
        ll r=n/(n/l);
        ll x=Sum(n/l)%mod;
        ans=(ans+x%mod*x%mod*(Sumphi(r)-Sumphi(l-1)+mod)%mod)%mod;
        l=r+1;
    }

    printf("%lld",ans%mod);

    return 0;
}

526互联

简单的数学题

简单的数学题