1 条题解
-
0
问题
组数据。每组数据给定 （），
求， 说明： 为 的约数个数。
题解
不容易想到，并且缺了不可的一种转变：
$d(ij)=\sum\limits_{x|i}\sum\limits_{y|j}\lbrack \gcd(x,y)=1 \rbrack$证明：
设 ，制造 需要分别从 和 抽取质因子。 从 中抽取的质因数乘积为 , 从 中抽取的质因数乘积为 。
若 需要的质因子在 和 都有，则优先在 中抽取，若还不够再从 中抽取（保证： 的唯一）。
若 同种质因子 , 在 和 中都有抽取，说明 中所有的 都被抽走了，则让来自 的 都变成1，则 缩水为 （保证： 和 互质），然而 和 是一一对应的。
故 和 一一对应。$=\sum\limits_{i=1}^n\sum\limits_{j=1}^m \sum\limits_{x|i}\sum\limits_{y|j}\lbrack \gcd(x,y)=1 \rbrack$ $\sum\limits_{i=1}^n \sum\limits_{x|i} = \sum\limits_{i=1}^n \sum\limits_{x=1}^n \lbrack x|i \rbrack = \sum\limits_{x=1}^n \sum\limits_{i=1}^n \lbrack x|i \rbrack = \sum\limits_{x=1}^n \lfloor \frac{n}{x} \rfloor$
同理： $\sum\limits_{j=1}^m \sum\limits_{y|j} = \sum\limits_{y=1}^m \lfloor \frac{m}{y} \rfloor$$= \sum\limits_{x=1}^n \sum\limits_{y=1}^m \lfloor \frac{n}{x} \rfloor \lfloor \frac{m}{y} \rfloor\lbrack \gcd(x,y)=1 \rbrack$ 代替，代替 $= \sum\limits_{i=1}^n \sum\limits_{j=1}^m \lfloor \frac{n}{i} \rfloor \lfloor \frac{m}{j} \rfloor \lbrack \gcd(i,j)=1 \rbrack$ $= \sum\limits_{i=1}^n\sum\limits_{j=1}^m \lfloor \frac{n}{i} \rfloor \lfloor \frac{m}{j} \rfloor \sum\limits_{d|\gcd(i,j)}\mu(d)$ $= \sum\limits_{i=1}^n\sum\limits_{j=1}^m \lfloor \frac{n}{i} \rfloor \lfloor \frac{m}{j} \rfloor \sum\limits_{d=1}^n \lbrack d|i \rbrack \lbrack d|j \rbrack \mu(d)$ $=\sum\limits_{d=1}^n \mu(d) \sum\limits_{i=1}^n \lfloor \frac{n}{i} \rfloor \lbrack d|i \rbrack\sum\limits_{j=1}^m \lfloor \frac{m}{j} \rfloor \lbrack d|j \rbrack$ $=\sum\limits_{d=1}^n \mu(d) \sum\limits_{i=1}^{\frac{n}{d}} \lfloor \frac{n}{id} \rfloor \sum\limits_{j=1}^{\frac{m}{d}} \lfloor \frac{m}{jd} \rfloor$ 设 $F(\frac{n}{d})= \sum\limits_{i=1}^{\frac{n}{d}} \lfloor \frac{n}{id} \rfloor$ ，通过观察，无妨设 ，即 $F(T)=\sum\limits_{i=1}^T \lfloor \frac{T}{i} \rfloor$ 可以预处理前缀和。
当 时， $F(7)=\frac{7}{1}+\frac{7}{2}+\frac{7}{3}+ \dots +\frac{7}{7}$
故 的初始化如下：F[0]=0;
for(int i=1;i<=N;i++)
for(int l=1,r;l<=i;l=r+1)
r=(i/(i/l)),
F[i]+=1ll*(r-l+1)*(i/l);$=\sum\limits_{d=1}^n \mu(d) F(\frac{n}{d})F(\frac{m}{d})$ 本题的推导过程经验：
1、要观察模拟，再决定要不要替换、怎么替换。
2、替换不是形式主义。具体代码如下：
#include<bits/stdc++.h> #define LL long long using namespace std; const int N=5e4; int pr, p[N+10];LL mu[N+10],F[N+10]; bool v[N+10]; void init() { memset(v,0,sizeof(v)); pr=0;mu[0]=0;mu[1]=1; for(int i=2;i<=N;i++) { if(!v[i]) p[++pr]=i, mu[i]=-1; for(int j=1;j<=pr&&p[j]*i<=N;j++) { v[i*p[j]]=true; if(i%p[j]==0) {mu[i*p[j]]=0; break;} mu[i*p[j]]=-mu[i]; } } for(int i=1;i<=N;i++)mu[i]+=mu[i-1]; F[0]=0; for(int i=1;i<=N;i++) for(int l=1,r;l<=i;l=r+1) r=(i/(i/l)), F[i]+=1ll*(r-l+1)*(i/l); } LL calc(int n, int m) { LL ans=0; for(int l=1,r;l<=n;l=r+1) { r=min(n/(n/l), m/(m/l)); ans+=(mu[r]-mu[l-1])*F[n/l]*F[m/l]; } return ans; } int main() { init(); int T;scanf("%d",&T); while(T--) { int n,m,k; scanf("%d%d", &n, &m);if(n>m)swap(n,m); printf("%lld\n", calc(n, m)); } return 0; }
- 1
