时间戳

首页 > 技术文章 > bzoj 3529

bzoj 3529

qdscwyy 2017-12-10 18:28 原文

	\subsubsection{例题4:}
	\href{http://www.lydsy.com/JudgeOnline/problem.php?id=3529}{BZOJ 3529: [Sdoi2014]数表}\\
	\href{http://blog.csdn.net/PoPoQQQ/article/details/42076231}{选择膜拜Po爷}\\
	\par 题目大意：令F(i)为i的约数和，给定n,m,a,求\\
		$$\sum_{F(d)\leq a}F((i,j)=d)$$
	因为a的限制非常讨厌，所以我们先忽略它的存在\\
	令$Z=min(n,m)$
	\begin{align*}
	\text{令}g(i)=&\sum\left[(x,y)=i \right]\\
	\text{那么显然有}g(i)=&\sum_{i|d}\mu(\frac{d}{i})\lfloor \frac{n}{d}\rfloor \lfloor \frac{m}{d}\rfloor \\
	\because (i,j)=&d,d=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}\\
	\text{由约数和定理得}F(d)=&(p_1^0+p_1^1+\cdots +p_1^{a_1})(p_2^0+p_2^1+\cdots +p_2^{a_2})\cdots (p_k^0+p_k^1+\cdots p_k^{a_k})\\
	\therefore F(pq)=&F(p)F(q),(p,q)=1\\
	\text{$F(i)$可}&\text{以利用线性筛在$O(n)$时间内处理出来，那么就有}\\
	ans=&\sum_{i=1}^{Z}F(i)g(i)\\
	=&\sum_{d=1}^{Z}\lfloor \frac{n}{d}\rfloor \lfloor \frac{m}{d}\rfloor \sum_{i|d}F(i)\mu(\frac{d}{i})
	\end{align*}
	然后我们可以发现最后这个式子的形式和上面非常像\\
	然后利用上述前缀和和枚举除法取值的方法就可以完成\\
	
	\par 可是题目中还有一个$a$的限制，
	我们可以发现对答案有贡献的只有$F(i)\leq a$$i$\\
	\par 可以离线来处理这个东西，
	将询问按照$a$从小到大排序，将$F(i)$按照从小到大的顺序排序，
	每次询问之前将所有$F(i)\leq a$插入并且用树状数组维护前缀和。
	当然还有一个需要注意的问题是取模\footnote{取模可以利用自然溢出$int$最后再对$2^{31}-1$取与即可}\\
	接连做了好几道题都有喜闻乐见的\textsl{除法分块\ref{2}}
	\newpage 
\begin{lstlisting}[language={[ANSI]C}]
#include<algorithm>
#include<iostream>
#include<cstdio>
#define N 100005
#define inf 0x7fffffff
#define ll long long 
using namespace std;
int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int Q,mx,cnt;
struct data{
    int n,m,a,id;
}q[N];
bool operator<(data a,data b){
    return a.a<b.a;
}
pair<int,int>F[N];
int pri[N],mu[N];
int ans[N],t[N];
bool mark[N];
void add(int x,int val){
    for(int i=x;i<=mx;i+=i&-i)t[i]+=val;
}
int query(int x){
    int tmp=0;for(int i=x;i;i-=i&-i)tmp+=t[i];return tmp;
}
int Query(int l,int r){
    return query(r)-query(l-1);
}
void getmu(){
    mu[1]=1;
    for(int i=2;i<=mx;i++){
        if(!mark[i])pri[++cnt]=i,mu[i]=-1;
        for(int j=1;j<=cnt&&pri[j]*i<=mx;j++){
            mark[pri[j]*i]=1;
            if(i%pri[j]==0){mu[pri[j]*i]=0;break;}
            else mu[pri[j]*i]=-mu[i];
        }
    }
    for(int i=1;i<=mx;i++)
        for(int j=i;j<=mx;j+=i)
            F[j].first+=i;
    for(int i=1;i<=mx;i++)F[i].second=i;
}
void solve(int x){
    int id=q[x].id,n=q[x].n,m=q[x].m;
    for(int i=1,j;i<=q[x].n;i=j+1){
        j=min(n/(n/i),m/(m/i));
        ans[id]+=(n/i)*(m/i)*Query(i,j);
    }
}
int main(){
    Q=read();
    for(int i=1;i<=Q;i++){
        q[i].n=read();q[i].m=read();q[i].a=read();
        q[i].id=i;if(q[i].n>q[i].m)swap(q[i].n,q[i].m);
        mx=max(mx,q[i].n);
    }
    getmu();int now=0;
    sort(q+1,q+Q+1);sort(F+1,F+mx+1);
    for(int i=1;i<=Q;i++){
      while(now+1<=mx&&F[now+1].first<=q[i].a){
      for(int j=F[++now].second;j<=mx;j+=F[now].second)
                add(j,F[now].first*mu[j/F[now].second]);
        }solve(i);
    }
    for(int i=1;i<=Q;i++)
        printf("%d\n",ans[i]&inf);
    return 0;
}
\end{lstlisting}

\subsubsection{例题5:}
\href{http://www.lydsy.com/JudgeOnline/problem.php?id=2154}{BZOJ 2154:Crash的数字表格}\\
据说和\href{https://www.luogu.org/problemnew/show/P3768}{\color{blue} "luogu P3768"}惊人的相似\\ 
\par 题目大意:给定$n,m$，求$$\sum_{i=1}^n\sum_{j=1}^m\left[ i,j\right] $$
\sout {感觉有点慌，完整的公式推导花了两页}
\subsubsection{例题6:}
\href{http://www.lydsy.com/JudgeOnline/problem.php?id=2693}{BZOJ 2693: jzptab}\\
据说和上题惊人的相似\\ 
\sout {就是上题加强了数据}
做法依旧很鬼畜
\end{document}

推荐阅读