[BZOJ3561] DZY Loves Math VI

推推柿子，得到答案是这个东东（我果然对莫比乌斯反演还不够熟悉啊QAQ）

\[\sum_{d=1}^n d^d \sum_{x=1}^{\lfloor \frac{n}{d} \rfloor} \mu(x) \cdot x^{2d} \sum_{i=1}^{\lfloor \frac{n}{dx} \rfloor} i^d \sum_{j=1}^{\lfloor \frac{m}{dx} \rfloor} j^d\]

（好累啊这个柿子好复杂，我就不写过程了）
然后暴力求，稍微处理一下后面那两坨东西，就是 \(O(nlogn)\) 啦。

一开始预处理后面那两坨东西直接快速幂就多了个log，作为信仰型选手直接交了发结果T了QAQ

//#pragma GCC optimize(2)
//#pragma GCC optimize(3)
#include<bits/stdc++.h>
#include<tr1/unordered_map>
#define LL long long
#define re register
#define fr(i,x,y) for(re int i=(x),z=y;i<=z;i++)
#define rf(i,x,y) for(int i=(x);i>=(y);i--)
#define frl(i,x,y) for(int i=(x);i<(y);i++)
using namespace std;
using namespace tr1;
const int N=500005;
const int INF=2147483647;
const int p=1e9+7;
int n,m;
int mu[N],b[N],L,pri[N];

void read(int &x){
    char ch=getchar();x=0;
    for(;ch<'0'||ch>'9';ch=getchar());
    for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+ch-'0';
}

inline void Add(LL &x,LL y){
    x+=y;
    while(x<0) x+=p;
    while(x>=p) x-=p;
}

inline LL qpow(LL a,int n){
    LL ans=1;
    for(LL sum=a;n;n>>=1,sum=sum*sum%p) if (n&1) ans=ans*sum%p;
    return ans;
}

void init(){
    mu[1]=1;
    frl(i,2,N){
        if (!b[i]) pri[++L]=i,mu[i]=-1;
        for(int j=1;j<=L&&i*pri[j]<N;j++){
            b[i*pri[j]]=1;
            if (i%pri[j]==0){
                mu[i*pri[j]]=0;
                break;
            }
            mu[i*pri[j]]=-mu[i];
        }
    }
}

LL sum[N],pw[N];
int main(){
    init();
    read(n);read(m);
    if (n>m) swap(n,m);
    LL ans=0;
    fr(i,1,m) pw[i]=1;
    fr(i,1,n){
        //LL sum1=0,sum2=0;
        fr(j,1,m/i) sum[j]=(sum[j-1]+pw[j]*j%p)%p,pw[j]=pw[j]*j%p;
        //Add(ans,sum1*sum2%p*qpow(i,i)%p);
        LL s=0;
        fr(j,1,n/i)
         Add(s,mu[j]*qpow(sum[j]-sum[j-1],2)%p*sum[n/i/j]%p*sum[m/i/j]%p);
        Add(ans,s*qpow(i,i)%p);
    }
    cout<<ans<<endl;
    return 0;
}

[BZOJ3561] DZY Loves Math VI

原文：https://www.cnblogs.com/ymzqwq/p/bzoj3561.html