題目傳送門

題目大意： 設 $s(i,j)={\sum }_{d|i,d|j}d$，求 ${\sum }_{i=1}^n{\sum }_{j=1}^{m}s(i,j)[s(i,j)\le a]$。

題解

顯然 $s(i,j)={\sum }_{d|i,d|j}d={\sum }_{d|\gcd (i,j)}d={\sigma }_1(\gcd (i,j))$，那么原柿子變為：
$$=\sum _{i=1}^n\sum _{j=1}^m{\sigma }_1(\gcd (i,j))[{\sigma }_1(\gcd (i,j))\le a]$$

設 $f(d)$ 表示有多少對 $i,j$ 的 $\gcd$ 為 $d$，$F(n)$ 表示有多少對 $i,j$ 的 $\gcd$ 是 $n$ 的倍數，那么有：
$$F(n)=\sum _{n|d}f(d)$$

考慮莫比烏斯反演，反演一下上面的柿子得到：
$$f(d)=\sum _{d|n}F(n)\mu (\frac{n}{d})$$

轉化一下原來的柿子，可以得到：
$$\begin{gathered} =\sum _{i=1}^{\min (n,m)}{\sigma }_1(i)[{\sigma }_1(i)\le a]\times f(i) \\ =\sum _{i=1}^{\min (n,m)}{\sigma }_1(i)[{\sigma }_1(i)\le a]\times \sum _{i|p}F(p)\mu (\frac{p}{d}) \end{gathered}$$

設 $j=\frac{p}{d}$，更換枚舉對象，有：
$$=\sum _{i=1}^{\min (n,m)}{\sigma }_1(i)[{\sigma }_1(i)\le a]\times \sum _{j=1}^{?\frac{\min (n,m)}{i}?}F(ij)\mu (j)$$

根據莫比烏斯反演的一般思想：兩個變量乘在一起是不好看的。于是設 $k=ij$，更換枚舉對象，有：
$$\sum _{k=1}^{\min (n,m)}F(k)\sum _{i|k}{\sigma }_1(i)[{\sigma }_1(i)\le a]\mu (\frac{k}{i})$$

顯然，$F(k)=?\frac{n}{k}??\frac{m}{k}?$，設 $g(k)={\sum }_{i|k}{\sigma }_1(i)[{\sigma }_1(i)\le a]\mu (\frac{k}{i})$，帶進去得：
$$\sum _{k=1}^{\min (n,m)}?\frac{n}{k}??\frac{m}{k}?g(k)$$

因為 $a$ 會變，也就是說 $g(k)$ 是會變的，只有當 ${\sigma }_1(i)\le a$ 時，${\sigma }_1(i)$ 才會產生貢獻。因為 ${\sigma }_1(i)$ 是不會變的，所以將上面的柿子移個項，$a\ge {\sigma }_1(i)$，那么如果 $a$ 是嚴格不下降的，那么 ${\sigma }_1(i)$ 的貢獻就有了單調性。

那么我們可以將 ${\sigma }_1(i)$ 和所有詢問排序，詢問按 $a$ 排序，那么每次動態更新 $g(k)$ 即可。

因為求解的時候需要求出 $g(k)$ 的前綴和，而這個前綴和會隨著 $g(k)$ 的更新有很大的改動，所以我們需要用一個樹狀數組來維護 $g(k)$ 的前綴和。

代碼如下：

#include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define maxn 100010 #define ll long long #define mod 2147483648llint t; struct que{int n,m,a,pos;}; que ask[20010]; int low[maxn],prime[maxn],tt=0,mu[maxn]; bool v[maxn]; struct node{int x,y;}; node sigma[maxn]; bool cmp1(node x,node y){return x.y<y.y;} bool cmp2(que x,que y){return x.a<y.a;} void work() {mu[1]=1;for(int i=2;i<=maxn-10;i++){if(!v[i])prime[++tt]=i,mu[i]=-1;for(int j=1;j<=tt&&i*prime[j]<=maxn-10;j++){v[i*prime[j]]=true;if(i%prime[j]==0)break;mu[i*prime[j]]=-mu[i];}}for(int i=1;i<=maxn-10;i++){sigma[i].x=i;for(int j=1;i*j<=maxn-10;j++)sigma[i*j].y+=i;}sort(sigma+1,sigma+maxn-10+1,cmp1); } ll tr[maxn]; inline int lowbit(int x){return x&(-x);} void add(int x,ll y) {for(;x<=maxn-10;x+=lowbit(x))tr[x]=(tr[x]+y)%mod; } ll sum(int x) {ll re=0;for(;x>=1;x-=lowbit(x))re=(re+tr[x])%mod;return re; } ll anss[20010];int main() {work();scanf("%d",&t);for(int i=1;i<=t;i++)scanf("%d %d %d",&ask[i].n,&ask[i].m,&ask[i].a),ask[i].pos=i;sort(ask+1,ask+t+1,cmp2);int now=1;for(int i=1;i<=t;i++){while(sigma[now].y<=ask[i].a&&now<=maxn-10){for(int j=1;sigma[now].x*j<=maxn-10;j++)add(sigma[now].x*j,(ll)sigma[now].y*mu[j]);now++;}int n=ask[i].n,m=ask[i].m,l=1,r;ll ans=0;while(l<=min(n,m)){r=min(n/(n/l),m/(m/l));ans=(ans+(sum(r)-sum(l-1)+mod)%mod*(ll)(n/l)*(ll)(m/l))%mod;l=r+1;}anss[ask[i].pos]=ans;}for(int i=1;i<=t;i++)printf("%lld\n",anss[i]); }

總結

以上是生活随笔為你收集整理的SDOI 2014 数表 题解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。