【Bzoj2820】YY的GCD

来源和评测点

一模一样的题目但数据弱化版:Bzoj2818 GCD-莫比乌斯2
Bzoj2820

题目

【题目大意】
神犇YY虐完数论后给傻×kAc出了一题给定N, M,求1<=x<=N, 1<=y<=M且gcd(x, y)为质数的(x, y)有多少对kAc这种
傻×必然不会了,于是向你来请教……
【输入格式】
多组输入
第一行一个整数T 表述数据组数接下来T行,每行两个正整数,表示N, M
【输出格式】
T行,每行一个整数表示第i组数据的结果
【输入样例】
2
10 10
100 100
【输出样例】
30
2791

分析1

莫比乌斯反演教程和题目分类参见:
【OI之路】11更高级数论-2莫比乌斯反演
其他莫比乌斯反演题目参见:Tag-莫比乌斯反演

即使分块也会T!需要优化了,主要是针对素数:

转载并修改自Hzwer

$ 假定n<m $
$$\sum_{isprime(p)} \sum_{a=1}^n \sum_{b=1}^m gcd(a,b)==p$$

简化为:

$$\sum_{isprime(p)} \sum_{a=1}^{\left \lfloor \frac{n}{p} \right \rfloor} \sum_{b=1}^{\left \lfloor \frac{m}{p} \right \rfloor}gcd(a,b)==1$$

————在我之前的教程中,下面直接被忽略————
$$
\sum_{isprime(p)}
\sum_{a=1}^{\left \lfloor \frac{n}{p} \right \rfloor}
\sum_{b=1}^{\left \lfloor \frac{m}{p} \right \rfloor}
\sum_{d|gcd(a,b)}\mu(d)
$$

$$
\sum_{isprime(p)}
\sum_{a=1}^{\left \lfloor \frac{n}{p} \right \rfloor}
\sum_{b=1}^{\left \lfloor \frac{m}{p} \right \rfloor}
\sum_{d|a \space and \space d|b}\mu(d)
$$
因为:
$$
\sum_{d|a \space and \space d|b}1 是等于后边的
{\left \lfloor \frac{n}{pd} \right \rfloor}
{\left \lfloor \frac{m}{pd} \right \rfloor}

$$
所以之前就直接得出了。

————-在我之前的教程中,上面直接被忽略—————
额不妨设n<=m,则可以变成:
$$
\sum_{isprime(p)}
\sum_{d=1}^{\left \lfloor \frac{n}{p} \right \rfloor}
\mu(d)
{\left \lfloor \frac{n}{pd} \right \rfloor}
{\left \lfloor \frac{m}{pd} \right \rfloor}
$$

上面的式子已经很好用了,但可以考虑加速:

将pd设为k

$$
\sum_{k=1}^{n}
\sum_{isprime(p) \space and \space p|k}
\mu(\frac{k}{p})
{\left \lfloor \frac{n}{k} \right \rfloor}
{\left \lfloor \frac{m}{k} \right \rfloor}
$$

$$
\sum_{k=1}^{n} G(k)
{\left \lfloor \frac{n}{k} \right \rfloor}
{\left \lfloor \frac{m}{k} \right \rfloor}
$$

$$
G(k)就是
\sum_{isprime(p) \space and \space p|k}
\mu(\frac{k}{p})
$$

$$
也就是k的所有质因数的\mu(\frac{k}{质因数})之和
$$
于是就优化到了可怕的O(N)~

那么接下来就是要解决G(k)的预处理了
简单粗暴的,使用暴力枚举素数来更新

代码1

4332 ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int mymin(int x,int y) {return x<y?x:y;}
typedef long long ll;
const int MAXNUM=10000000,MAXPR=1000000;
int prime[MAXPR],pr;
ll mu[MAXNUM+10];
bool v[MAXNUM+10];
int G[MAXNUM+10];
void getmu()
{
mu[1]=1;pr=0;
memset(v,1,sizeof(v));
for(int i=2;i<=MAXNUM;i++)
{
if(v[i]==1) prime[++pr]=i,mu[i]=-1;
for(int j=1;j<=pr;j++)
{
ll tt=ll(i)*ll(prime[j]);
if(tt>ll(MAXNUM)) break;
v[tt]=0;
if(i%prime[j]==0)
{
mu[tt]=0;
break;
}
else mu[tt]=-mu[i];
}
}
for(int i=1;i<=pr;i++)
{
int p=prime[i];
for(int j=1;ll(j)*ll(p)<=ll(MAXNUM);j++)
G[j*p]+=mu[j];
}
for(int i=1;i<=MAXNUM;i++) G[i]+=G[i-1];
}
ll calc(int n,int m)
{
ll ans=0;
if(n>m) swap(n,m);
int t=1;
int last;
for(int k=1;k<=n;k=last+1)
{
last=mymin(n/(n/k),m/(m/k));
ans+=(G[last]-G[k-1])*ll(n/k)*ll(m/k);
}
return ans;
}
int main()
{
getmu();
int T;scanf("%d",&T);
while(T--)
{
int n,m;scanf("%d%d",&n,&m);
printf("%lld\n",calc(n,m));
}
}

分析2

然而,利用莫比乌斯函数的性质和G(k)的性质,
可以得到这样的规律(用了足足一节数学课):
if(i%prime[j]==0) G[tt]=mu[i];
else G[tt]=-G[i]+mu[i];

代码2

3476 ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int mymin(int x,int y) {return x<y?x:y;}
typedef long long ll;
const int MAXNUM=10000000,MAXPR=1000000;
int prime[MAXPR],pr;
ll mu[MAXNUM+10];
bool v[MAXNUM+10];
int G[MAXNUM+10];
void getmu()
{
mu[1]=1;pr=0;
memset(v,1,sizeof(v));
for(int i=2;i<=MAXNUM;i++)
{
if(v[i]==1) prime[++pr]=i,mu[i]=-1,G[i]=1;
for(int j=1;j<=pr;j++)
{
ll tt=ll(i)*ll(prime[j]);
if(tt>ll(MAXNUM)) break;
v[tt]=0;
if(i%prime[j]==0)
{
mu[tt]=0;
G[tt]=mu[i];
break;
}
else
{
mu[tt]=-mu[i];
G[tt]=-G[i]+mu[i];
}
}
}
for(int i=1;i<=MAXNUM;i++) G[i]+=G[i-1];
}
ll calc(int n,int m)
{
ll ans=0;
if(n>m) swap(n,m);
int t=1;
int last;
for(int k=1;k<=n;k=last+1)
{
last=mymin(n/(n/k),m/(m/k));
ans+=(G[last]-G[k-1])*ll(n/k)*ll(m/k);
}
return ans;
}
int main()
{
getmu();
int T;scanf("%d",&T);
while(T--)
{
int n,m;scanf("%d%d",&n,&m);
printf("%lld\n",calc(n,m));
}
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/2017-11/YY的GCD.html
转载请注明出处,谢谢!

给我投食吧,您的支持将鼓励我继续创作!