第一道自己认真做的数论
有两种方法, 默认 \((N<M)\)
方法一:
我们需要求:\[\sum\limits_{i=1}^N \sum\limits_{j=1}^M [gcd(i,j)=prime]\]
我们会想到枚举其中的素数:\[\sum\limits_{p\ \epsilon \ \ prime} \sum\limits_{i=1}^N \sum\limits_{j=1}^M [gcd(i,j)=p]\]
再一步变形:\[\sum\limits_{p\ \epsilon \ \ prime} \sum\limits_{i=1}^N \sum\limits_{j=1}^M [gcd(\frac{i}{p},\frac{j}{p})=1]\]
\[\sum\limits_{p\ \epsilon \ \ prime} \sum\limits_{i=1}^{\left\lfloor \frac{N}{p} \right\rfloor} \sum\limits_{j=1}^{\left\lfloor\frac{M}{p}\right\rfloor} [gcd(i,j)=1]\]
是不是看到中括号里面的东西想到了什么? 莫比乌斯函数~~
因为莫比乌斯函数的性质:\[\sum\limits_{d|n} \mu (d)=[n=1]\]
所以原式可化为:\[\sum\limits_{p\ \epsilon \ \ prime} \sum\limits_{i=1}^{\left\lfloor\frac{N}{p}\right\rfloor} \sum\limits_{j=1}^{\left\lfloor\frac{M}{p}\right\rfloor} \sum\limits_{d|gcd(i,j)} \mu (d)\]
我们按照套路把 \(d\) 提前, 其中 \(d|gcd(i,j)\) 这个条件可以转化成 \(d|i,d|j\), 我们就枚举 \(d\):\[\sum\limits_{p\ \epsilon \ \ prime} \sum\limits_{d=1}^{\left\lfloor\frac{N}{p}\right\rfloor} \mu (d) \sum\limits_{i=1}^{\left\lfloor\frac{N}{p}\right\rfloor} [d|i] \sum\limits_{j=1}^{\left\lfloor\frac{M}{p}\right\rfloor} [d|j]\]
根据整出分块, 没学过的可以看看我的其他博客, 我们就可以把最后两个 \(\sum\) 消去了:\[\sum\limits_{p\ \epsilon \ \ prime} \sum\limits_{d=1}^{\left\lfloor\frac{N}{p}\right\rfloor} \mu (d) \left\lfloor \frac{N}{d\times p} \right\rfloor \left\lfloor \frac{M}{d\times p} \right\rfloor\]
这里我们再用一个小技巧, 我们用 \(T\) 代替 \(d\times p\):
\[\sum\limits_{p\ \epsilon \ \ prime} \sum\limits_{T=1}^N \mu (\frac{T}{p}) \left\lfloor \frac{N}{T} \right\rfloor \left\lfloor \frac{M}{T} \right\rfloor\]
稍微变一下:\[\sum\limits_{T=1}^N \sum\limits_{p\ \epsilon \ \ prime} \mu (\frac{T}{p}) \left\lfloor \frac{N}{T} \right\rfloor \left\lfloor \frac{M}{T} \right\rfloor\]
这样的话, 我们就先线性筛出 \(\mu\) 函数, 然后把 \(\sum\limits_{p\ \epsilon \ \ prime} \mu (\frac{T}{p})\) 处理出来, 做一下前缀和, 就可以用整除分块来 \(O(\sqrt n)\) 回答每个询问了
接下来是美滋滋的代码时间~~~
- #include<iostream>
- #include<cstdio>
- #define N 10000007
- #define int long long
- using namespace std;
- int T,n,m,ans,cnt;
- int mu[N],prime[N>>2],num[N];
- bool isp[N];
- void Get_mu()
- {
- mu[1]=1;
- for(int i=2;i<=N-7;++i)
- {
- if(!isp[i])
- {
- prime[++cnt]=i;
- mu[i]=-1;
- }
- for(int j=1;j<=cnt&&(prime[j]*i)<=N-7;++j)
- {
- isp[i*prime[j]]=1;
- if(i%prime[j]==0)
- break;
- else
- mu[i*prime[j]]=-mu[i];
- }
- }
- for(int i=1;i<=cnt;++i)
- {
- int res=1;
- for(int j=prime[i];j<=N-7;j+=prime[i],++res)
- num[j]+=mu[res];
- }
- for(int i=2;i<=N-7;++i)
- num[i]+=num[i-1];
- }
- signed main()
- {
- Get_mu();
- scanf("%lld",&T);
- while(T--)
- {
- scanf("%lld%lld",&n,&m);
- if(n>m)
- swap(n,m);
- ans=0;
- for(int l=1,r;l<=n;l=r+1)
- {
- r=min(n/(n/l),m/(m/l));
- ans+=(num[r]-num[l-1])*(n/l)*(m/l);
- }
- printf("%lld\n",ans);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3107171.html