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)$
egin{align*}
ext{令}g(i)=&sumleft[(x,y)=i
ight]\
ext{那么显然有}g(i)=&sum_{i|d}mu(frac{d}{i})lfloor frac{n}{d}
floor lfloor frac{m}{d}
floor \
ecause (i,j)=&d,d=p_1^{a_1}p_2^{a_2}cdots p_k^{a_k}\
ext{由约数和定理得}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})\
herefore F(pq)=&F(p)F(q),(p,q)=1\
ext{$F(i)$可}& ext{以利用线性筛在$O(n)$时间内处理出来，那么就有}\
ans=&sum_{i=1}^{Z}F(i)g(i)\
=&sum_{d=1}^{Z}lfloor frac{n}{d}
floor lfloor frac{m}{d}
floor 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$取与即可}\
接连做了好几道题都有喜闻乐见的 extsl{除法分块
ef{2}}
ewpage
egin{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
",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}^nsum_{j=1}^mleft[ i,j
ight] $$
sout {感觉有点慌，完整的公式推导花了两页}
subsubsection{例题6:}
href{http://www.lydsy.com/JudgeOnline/problem.php?id=2693}{BZOJ 2693: jzptab}\
据说和上题惊人的相似\
sout {就是上题加强了数据}
做法依旧很鬼畜
end{document}