神犇YY虐完数论后给傻×kAc出了一题
给定N, M,求1<=x<=N, 1<=y<=M且gcd(x, y)为质数的(x, y)有多少对
kAc这种傻×必然不会了,于是向你来请教……
链接🔗
「Luogu-P2257」YY的GCD
题解
这题公式巨长,理解了好久才搞懂
先列出我们所需要求的东西是什么
∑p∈prime∑i=1n∑j=1m[gcd(i,j)=p]
首先定义两个函数
f(d)=∑i=1n∑j=1m[gcd(i,j)=d]
g(d)=∑i=1n∑j=1m[d∣gcd(i,j)]
根据 g(d) 的值根据整除定义,可以得出 ⌊dn⌋⌊dm⌋
根据 g(d) 的定义,可以得出 g(d)=∑n∣df(d)
然后通过莫比乌斯反演可以得到 f(n)=∑n∣dμ(⌊nd⌋)g(d)
接下来 我们就开始对原公式进行化简
ans=p∈prime∑i=1∑nj=1∑m[gcd(i,j)=p]
ans=p∈prime∑f(p)
ans=p∈prime∑p∣d∑μ(⌊pd⌋)g(d)
这里设 n<m ,然后将枚举项设为d
ans=p∈prime∑d∑⌊pn⌋μ(d)g(dp)
然后把g(dp) 拆开来
ans=p∈prime∑d∑⌊pn⌋μ(d)⌊dpn⌋⌊dpm⌋
把令dp=t
ans=p∈prime∑d∑⌊pn⌋μ(d)⌊tn⌋⌊tm⌋
因为 dp=t ,所以后面部分提出来
t=1∑n⌊tn⌋⌊tm⌋p∣t,p∈prime∑μ(pt)
公式到这就化简完毕了
很明显,前面部分可以用数论分块做到 O((n)) ,我们来讨论一下后面部分
μ是可以线性筛出来的,对于任意一个质数p,我们可以也可以通过筛出 ∑p∣t,p∈primeμ(pt) 时间复杂度大概为 O(n loglog n)
最后做个前缀和,就可以配合前面的式子进行数论分块了
代码
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxd = 1e7+10;
int m,n,ans,k,t;
int mu[maxd], prime[maxd],summu[maxd],cnt,f[maxd];
bool vis[maxd];
void init()
{
mu[1] = 1;
for(int i=2;i<maxd;i++)
{
if(!vis[i]) prime[++cnt] = i, mu[i] = -1;
for(int j=1;j<=cnt && i*prime[j] <= maxd;j++)
{
vis[i*prime[j]] = 1;
if(i%prime[j] == 0) break;
mu[i*prime[j]] = -mu[i];
}
}
for(int i=1;i<=cnt;i++)
for(int j=1;prime[i]*j<maxd;j++)
f[j*prime[i]] += mu[j];
//前缀和
for(int i=1;i<maxd;i++) summu[i] = summu[i-1] + f[i];
}
long long sum(int m,int n) //数论分块
{
long long t = min(n, m), ans = 0;
for (int i = 1, j = 1; i <= t; i = j + 1)
{
j = min(n / ( n / i), m / (m / i));
ans += (summu[j] - summu[i - 1]) * (long long)(n / i) * (m / j);
}
return ans;
}
int main()
{
// freopen("a.in","r",stdin);
// freopen("k.out","w",stdout);
init();scanf("%d",&t);
for(int i=1;i<=t;i++)
{
scanf("%d %d",&n,&m);
printf("%lld\n",sum(n,m));
}
return 0;
}