题目描述
神犇YY虐完数论后给傻×kAc出了一题
给定N, M,求1<=x<=N, 1<=y<=M且gcd(x, y)为质数的(x, y)有多少对
kAc这种傻×必然不会了,于是向你来请教……
多组输入
输入输出格式
输入格式:
第一行一个整数T 表述数据组数
接下来T行,每行两个正整数,表示N, M
输出格式:
T行,每行一个整数表示第i组数据的结果
输入输出样例
输入样例#1:
2
10 10
100 100
输出样例#1:
30
2791
说明
T = 10000
N, M <= 10000000
-----------------------------------------------------------------
这是我做得第一道莫比乌斯反演的题
虽然已经掌握了
莫比乌斯反演的证明
但是
显然这还差很多
因为
我不会应用到实际推演当中
当我再次弄懂该如何推演的时候
我自认为可以写出来的
但是
并没有
我发现我在很多细节上
还是很拿不准的
于是
再次卑微
----------------------------------------------------
解题思路:
如何实现前缀和呢??
这里就用到了整除分块(这也是这道题困扰我很久很久时间的部分)
那么什么是整除分块呢??
整除分块————一个莫比乌斯反演的题基本都会涉及到的小知识点,其实,是很有必要使之成为前置知识点中的其中之一
- 可以用到整除分块的形式,大致是这样的:
∑i=1n⌊n/i⌋
- 这个式子,O(n)计算是非常显然的。但,有的时候因为多组数据的要求,可能O(n)并不是正确的时间复杂度。那么这个时候,我们就有一种O(√n)
的做法。这就是:整除分块!
- 对于每一个⌊n/i⌋
我们可以通过打表
(或理性的证明)可以发现:有许多⌊ni⌋的值是一样的,而且它们呈一个块状分布;再通过打表之类的各种方法,我们惊喜的发现对于每一个值相同的块,它的最后一个数就是n/(n/i)
。得出这个结论后,我们就可以做的O(√n)
处理了。
整除分块的代码如下:
for(int l=,r;l<=n;l=r+)
{
r=n/(n/l);
ans+=(r-l+)*(n/l);
}
那么现在我终于理解本题的代码了
#include<bits/stdc++.h>
#define N 10000100
using namespace std; inline void read(int &x)
{
x=;
static int p;p=;
static char c;c=getchar();
while(!isdigit(c)){if(c=='-')p=-;c=getchar();}
while(isdigit(c)) {x=(x<<)+(x<<)+(c-);c=getchar();}
x*=p;
} inline void print(long long x)
{
static int cnt;
static int a[];
cnt=;
do
{
a[++cnt]=x%;
x/=;
}
while(x);
for(int i=cnt;i>=;i--)
putchar(a[i]+'');
puts("");
} bool vis[N];//判断是否为素数
long long sum[N];
int prim[N];//存素数
int mu[N],g[N];//mu存μ
int cnt;//素数个数(筛素数用的,不用管啊)
void get_mu(int n)
{
mu[]=;
for(int i=;i<=n;i++)//线性筛??
{
if(!vis[i])//没有被访问过,即为素数
{
mu[i]=-;//素数的质因数只可能是它自己,所以,他的μ值一定为-1
prim[++cnt]=i;//prim数组是用来记录素数的 ,cnt累计素数个数
}
for(int j=;j<=cnt&&prim[j]*i<=n;j++)//和欧拉筛很像吧,就是用欧拉筛的思路的
//j是用来枚举素数的 ,prim[j]*i是筛合数,并保证筛掉的合数在应求的范围内(没有越界,没有浪费时间和空间)
{
vis[i*prim[j]]=;//打标记:筛掉合数
if(i%prim[j]==)//当前的数可以被质数整除的话 (在下一行)
break;//那么i%prim[j]的质因数中有两个相同的,也就是说i%prim[j]的μ值是0,(数组开的全局变量,默认初始值为0,所以就可以不用管它)
else
mu[prim[j]*i]=-mu[i];//不能被整除 i和prim[j]互质,得到的合数的 μ值为i的μ值的相反数
}
}
for(int j=;j<=cnt;j++)//如果把最终得到的公式看作是两层循环的话,那么这里相当于最里面的那层循环,也就是最右面的Σ
for(int d=;d*prim[j]<=n;d++)
g[d*prim[j]]+=mu[d]; //μ值累加
for(int i=;i<=n;i++)//而这个相当于最外面的循环,即最左面的Σ
{
sum[i]=sum[i-]+(long long)g[i];//据说这里是用来计算前缀和的??! !!我大概明白了!!!
}
}
int n,m;
int main()
{
int t;
read(t);
get_mu();
while(t--)
{
read(n);read(m);
if(n>m)swap(n,m);
static long long ans;
ans=;
for(int T=,d;T<=n;T=d+)
{
d=min(n/(n/T),m/(m/T));
ans+=1ll*(n/T)*(m/T)*(sum[d]-sum[T-]);//1ll是把int变成long long然后再赋值给long long,是怕int不够存的
//知道看到这个位置,我才知道sum的含义。sum是指Σ(p|T)μ(T/p) //这里是啥啊????!
//这里大概是整除分块,有许多[n/i]的值是一样的,而且它们呈一个块状分布
}
print(ans);
}
return ;
}