【SDOI2014】数表(table)

2019-11-06 06:06:13

字体：大中小

来源：转载

供稿：网友

Description

这里写图片描述

Solution

很明显可以发现，n和m交换是不会影响答案的，我们可以先设一个f(x)=∑d|xd $f(x)=/sum_{d|x}d$ 表示i $i$ 的约数和，还有一个数组g(x)=∑ni=1∑mj=1(gcd(i,j)=x) $g(x)=/sum_{i=1}^{n}/sum_{j=1}^{m}(gcd(i,j)=x)$ ，而答案明显就是∑ni=1f(i)∗g(i) $/sum_{i=1}^{n}f(i)*g(i)$ ，看到了g(x) $g(x)$ 中的gcd $gcd$ 可以很快能够想到莫比乌斯反演，对g(x) $g(x)$ 我们化简一下： g(x)=∑⌊ni⌋i=1∑⌊mj⌋j=1∑d=gcd(i,j)μ(d) $g(x)=/sum_{i=1}^{/lfloor{n/over i}/rfloor}/sum_{j=1}^{/lfloor{m/over j}/rfloor}/sum_{d=gcd(i,j)}μ(d)$ =∑x|dμ(d)⌊nd⌋⌊md⌋ $=/sum_{x|d}μ(d){/lfloor{n/over d}/rfloor}{/lfloor{m/over d}/rfloor}$ 然后把化简后的g(x) $g(x)$ 代入求答案得： ans=∑ni=1f(i)∑x|dμ(d)⌊nd⌋⌊md⌋ $ans=/sum_{i=1}^{n}f(i)/sum_{x|d}μ(d){/lfloor{n/over d}/rfloor}{/lfloor{m/over d}/rfloor}$ =∑nd=1⌊nd⌋⌊md⌋∑i|df(i)∗μ(di) $=/sum_{d=1}^{n}{/lfloor{n/over d}/rfloor}{/lfloor{m/over d}/rfloor}/sum_{i|d}f(i)*μ({d/over i})$ 我们令h(i)=∑i|df(i)∗μ(di) $h(i)=/sum_{i|d}f(i)*μ({d/over i})$ ，因为只有当f(x)≤a $f(x)≤a$ 的时候才有贡献，所以，把所有询问按照a $a$ 从小到大离线排序，然后把符合条件的f(x) $f(x)$ 一个个加入进去，而对于h(i) $h(i)$ 我们可以用前缀和来维护。

Code

#include<string.h>#include<iostream>#include<algorithm>#include<math.h>#include<stdio.h>using namespace std;#define fo(i,a,b) for(i=a;i<=b;i++)const int maxn=1e5+5;typedef long long ll;struct arr{ int n,m,mx,bh;}a[20005];struct da{ int f,PR;}f[maxn];bool cmp(arr x,arr y){return x.mx<y.mx;}bool cmp1(da x,da y){return x.f<y.f;}bool p[maxn];int cas,n,m,i,j,k,mx,s[maxn],mu[maxn],t[maxn];ll mo,ans[maxn];void screen(int mx){ int i,j,k; fo(i,2,mx){ if(!p[i]) s[++s[0]]=i,mu[i]=-1; fo(j,1,s[0]){ k=i*s[j]; if(k>mx) break; p[k]=true; if(i%s[j]==0){ mu[k]=0; break; } mu[k]=mu[i]*mu[s[j]]; } } mu[1]=1; fo(i,1,mx){ f[i].pr=i; for(j=i;j<=mx;j+=i) f[j].f+=i; }}void add(int x,int sum){ for(x=x;x<=mx;x+=x&(-x)) t[x]+=sum;}int get(int x){ int sum; sum=0;if(x==0) return 0; for(x=x;x;x-=x&(-x)) sum+=t[x]; return sum;}void solve(int x){ int n,m,bh,i,j; n=a[x].n,m=a[x].m,bh=a[x].bh; for(i=1;i<=n;i=j+1){ j=min(n/(n/i),m/(m/i)); ans[bh]+=(n/i)*(m/i)*(get(j)-get(i-1)); }}int main(){ freopen("table.in","r",stdin); freopen("table.out","w",stdout); mo=1;fo(i,1,31) mo=mo*2; scanf("%d",&cas); fo(i,1,cas){ scanf("%d%d%d",&a[i].n,&a[i].m,&a[i].mx); if(a[i].n>a[i].m) swap(a[i].n,a[i].m); a[i].bh=i;mx=max(mx,a[i].n); } screen(mx); sort(a+1,a+cas+1,cmp); sort(f+1,f+mx+1,cmp1); j=0; fo(i,1,cas){ while(j<mx&&f[j+1].f<=a[i].mx){ j++; for(k=f[j].pr;k<=mx;k+=f[j].pr){ add(k,f[j].f*mu[k/f[j].pr]); } } solve(i); } fo(i,1,cas) printf("%lld/n",ans[i]%mo);}

上一篇：深入springMVC源码------文件上传源码解析(下篇)

下一篇：深入springMVC------文件上传源码解析(上篇)

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注