bzoj4176 Lucas 的数论

$$\begin{align}& \sum_{i=1}^n\sum_{j=1}^nf(ij) \\= & \sum_{i=1}^n\sum_{j=1}^n\sum_{d=1}^{n^2}[\frac d {\gcd(i,d)}|j] \\= & \sum_{i=1}^n \sum_{d=1}^{n^2}\lfloor\frac{n*\gcd(i,d)}d\rfloor \\= & \sum_{d=1}^n\sum_{i=1}^{\lfloor\frac nd \rfloor}\sum_{j=1}^{\lfloor\frac{n^2}d\rfloor} \lfloor\frac nj\rfloor e(\gcd(i,j)) \\= & \sum_{d=1}^n\sum_{i=1}^{\lfloor\frac nd \rfloor}\sum_{j=1}^n\lfloor \frac n j\rfloor\sum_{x|\gcd(i,j)} \mu(x) \\= & \sum_{x=1}^n\mu(x)\sum_{d=1}^n\lfloor\frac n{dx}\rfloor\sum_{j=1}^{\lfloor\frac nx\rfloor}\lfloor\frac n{jx}\rfloor \\= & \sum_{x=1}^n\mu(x)(\sum_{j=1}^{\lfloor\frac nx\rfloor}\lfloor\frac n {jx} \rfloor)^2 \end{align}$$
对后面的部分进行下底函数分块，一段 $\mu(x)$的和用杜教筛求出。

#include<cstdio>
#include<algorithm>
using namespace std;
#define LL long long
const int maxn=3000000,p=1000007,mod=1000000007,oo=0x3f3f3f3f;
struct hash_table
{int fir[p+10],ne[maxn],val[maxn],ans[maxn],tot;int find(int n){for (int i=fir[n%p];i;i=ne[i])if (val[i]==n) return ans[i];return oo;}void ins(int n,int x){int y=n%p;tot++;ne[tot]=fir[y];fir[y]=tot;val[tot]=n;ans[tot]=x;}
}h;
int inc(int x,int y)
{x+=y;return x>=mod?x-mod:x;
}
int dec(int x,int y)
{x-=y;return x<0?x+mod:x;
}
int summu(int n)
{if (!n) return 0;int ret=h.find(n);if (ret!=oo) return ret;ret=1;for (int i=2,j;i<=n;i=j+1){j=n/(n/i);ret-=(j-i+1)*summu(n/i);}h.ins(n,ret);return ret;
}
int sumdiv(int n)
{int ret=0;for (int i=1,j;i<=n;i=j+1){j=n/(n/i);ret=inc(ret,(LL)(j-i+1)*(n/i)%mod);}return ret;
}
int main()
{int n,x,y,ans=0;scanf("%d",&n);//n=1000000000;for (int i=1,j;i<=n;i=j+1){j=n/(n/i);x=dec(summu(j),summu(i-1));y=sumdiv(n/i);ans=inc(ans,(LL)x*y%mod*y%mod);}printf("%d\n",ans);
}