【bzoj3529】 Sdoi2014

μhttp://www.lydsy.com/JudgeOnline/problem.php?id=3529 (题目链接)

题意

　　多组询问，每次给出${n,m,a}$。求$${\sum_{i=1}^n\sum_{j=1}^m[\sum_{d|i,d|j}d<=a]\sum_{d|i,d|j}d}$$

Solution

　　PoPoQQQ的看不懂，我还是比较适合套路→_→：http://blog.csdn.net/FZHvampire/article/details/50964639

　　有${a}$的限制很不好做，我们不妨先来看看如果没有${a}$的限制，是个什么情况。

\begin{aligned} & \sum_{i=1}^n\sum_{j=1}^m\sum_{d|i,d|j}d \\ =&\sum_{i=1}^n\sum_{j=1}^m\sum_{d=1}^{min(n,m)}f(d)[gcd(i,j)=d] \end{aligned}

　　这里${f(d)}$表示${d}$的约数和，由约数和定理：$${d=p_1^{a_1}p_2^{a_2}p_3^{a_3}······p_k^{a_k}}$$

$${f(d)=(p_1^0+p_1^1+······+p_1^{a_1})(p_2^0+p_2^1+······+p_2^{a_2})······(p_k^0+p_k^1+······+p_k^{a_k})}$$

　　我们发现当${p,q}$互质时，${f(pq)=f(p)f(q)}$，${f}$是个积性函数。也就是说${f}$可以线性筛求解，具体求法可以看代码。回到上面的问题，我们继续变化这个式子。

\begin{aligned} &\sum_{i=1}^n\sum_{j=1}^m\sum_{d=1}^{min(n,m)}f(d)[gcd(i,j)=d] \\ =&\sum_{d=1}^{min(n,m)}f(d)\sum_{i=1}^{\lfloor{n/d}\rfloor}\sum_{j=1}^{\lfloor{m/d}\rfloor}[gcd(i,j)=1] \\ =&\sum_{d=1}^{min(n,m)}f(d)\sum_{t=1}^{min(\lfloor{n/d}\rfloor,\lfloor{m/d}\rfloor)}μ(t)\lfloor\frac{n}{dt}\rfloor\lfloor\frac{m}{dt}\rfloor \end{aligned}

　　我们令${Q=dt}$，先枚举${Q}$，得到：$${\sum_{Q=1}^{min(n,m)}\lfloor\frac{n}{Q}\rfloor\lfloor\frac{m}{Q}\rfloor\sum_{d|Q}f(d)μ(\frac{Q}{d})}$$

　　我们对${f}$和${μ}$函数的狄利克雷卷积${g(Q)=\sum_{d|Q}f(d)μ(\frac{Q}{d})}$预处理前缀和，前面的${\lfloor\frac{n}{Q}\rfloor\lfloor\frac{m}{Q}\rfloor}$分块，那么这个式子的计算就达到了${\sqrt{n}}$。

　　考虑如何加入限制${a}$。

　　我们可以离线，将询问按照${a}$从小到大排序，${f}$函数按照从小到大排序。询问的时候，我们就动态维护一个树状数组${c}$。树状数组的每一位${c[x]}$存的是卷积${g(x)}$中${f(d)}$不超过${a}$的数之和。数据组数为${T}$，询问复杂度${O(T\sqrt{n}logn)}$

细节

　　这题复杂度有点卡，对于取模运算我们可以对${int}$自然溢，最后再${\&2147483647}$就可以了。

代码

// bzoj3994

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<vector>

#include<cmath>

#define LL long long

#define inf 2147483647

#define Pi acos(-1.0)

#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);

using namespace std;

const int maxn=100010;

int mu[maxn],e[maxn],ans[maxn],c[maxn],vis[maxn],p[maxn],t[maxn],g[maxn];

struct F {int d,num;}f[maxn];

struct Q {int n,m,a,id;}q[maxn];

bool cmpT(Q a,Q b) {return a.a<b.a;}

bool cmpt(F a,F b) {return a.d<b.d;}

int lowbit(int x) {return x&-x;}

int power(int a,int b) {

	int res=1;

	while (b) {

		if (b&1) res*=a;

		a*=a,b>>=1;

	}

	return res;

}

void add(int x,int val) {

	for (int i=x;i<maxn;i+=lowbit(i)) c[i]+=val;

}

int query(int x) {

	int s=0;

	for (int i=x;i>=1;i-=lowbit(i)) s+=c[i];

	return s;

}

int main() {

	mu[1]=1;f[1].d=f[1].num=1;

	for (int i=2;i<maxn;i++) {

		f[i].num=i;

		if (!vis[i]) mu[i]=-1,f[i].d=t[i]=1+i,g[i]=1,p[++p[0]]=i;

		for (int j=1;j<=p[0] && i*p[j]<maxn;j++) {

			vis[i*p[j]]=1;

			if (i%p[j]==0) {

				mu[i*p[j]]=0;

				g[i*p[j]]=g[i]+1;

				t[i*p[j]]=t[i]+power(p[j],g[i]+1);

				f[i*p[j]].d=f[i].d/t[i]*t[i*p[j]];

				break;

			}

			else {

				mu[i*p[j]]=-mu[i];

				f[i*p[j]].d=f[i].d*f[p[j]].d;

				g[i*p[j]]=1;t[i*p[j]]=p[j]+1;

			}

		}

	}

	int T;scanf("%d",&T);

	for (int i=1;i<=T;i++) scanf("%d%d%d",&q[i].n,&q[i].m,&q[i].a),q[i].id=i;

	sort(q+1,q+1+T,cmpT);

	sort(f+1,f+maxn,cmpt);

	for (int now=0,i=1;i<=T;i++) {

		while (now+1<maxn && f[now+1].d<=q[i].a) {   //now忘记+1还过了数据，这是有多水→_→

			now++;

			for (int j=1;j*f[now].num<maxn;j++)

				add(j*f[now].num,mu[j]*f[now].d);

		}

		int n=q[i].n,m=q[i].m;

		if (n>m) swap(n,m);

		for (int j=1,k;j<=n;j=k+1) {

			k=min(n/(n/j),m/(m/j));

			ans[q[i].id]+=(n/j)*(m/j)*(query(k)-query(j-1));

		}

		ans[q[i].id]&=inf;

	}

	for (int i=1;i<=T;i++) printf("%d\n",ans[i]);

	return 0;

}

巴特西

【bzoj3529】 Sdoi2014—数表

题意

Solution

细节

代码

最新文章

热门文章