P2257

发表于 更新于 分类于
YY的GCD

YY的GCD

是在是受不了了。。。为什么数论题我都要调啊。。。

这个素数的数量开到接近 $\dfrac{n}{\ln n}$ 的 6.8e5 都不够用是个什么操作？？？？

然后好像因为数组连续的问题这个空间就直接跳到了后面的前缀和 $s$ 数组上，导致一开始 $s$ 的初值就非常大，然后怎么调也调不出来。。。

真就被诅咒了还。。。。

式子已经反复推过 $n$ 遍了。。。随便写写。。。$\mathcal{P}$ 代表质数集合。

$$\begin{aligned}& \sum_{x=1}^{n}\sum_{y=1}^{m}[\gcd(x,y)\in \mathcal{P}] \\ =&\sum_{p\in \mathcal{P}}\sum_{x=1}^{\lfloor\frac{n}{p}\rfloor}\sum_{y=1}^{\lfloor\frac{m}{p}\rfloor}[\gcd(x,y)=1] \\ =&\sum_{p\in \mathcal{P}}\sum_{x=1}^{\lfloor\frac{n}{p}\rfloor}\sum_{y=1}^{\lfloor\frac{m}{p}\rfloor}\sum_{d\mid \gcd(x,y)}\mu(d) \\ =& \sum_{p\in\mathcal{P}}\sum_{d=1}\mu(d)\sum_{x=1}^{\lfloor\frac{n}{pd}\rfloor}\sum_{y=1}^{\lfloor\frac{m}{pd}\rfloor}1 \\=& \sum_{p\in\mathcal{P}}\sum_{d=1}\mu(d)\lfloor\dfrac{n}{pd}\rfloor\lfloor\dfrac{m}{pd}\rfloor\end{aligned}$$

接下来我们设 $T=pd$，然后 $d=\dfrac{T}{p}$，搞进去再换序求和一波。

$$\begin{aligned}=& \sum_{T=1}^{\min(n,m)}\sum_{p\in \mathcal{P},p\mid T}\mu(\dfrac{T}{p})\lfloor\dfrac{n}{T}\rfloor\lfloor\dfrac{m}{T}\rfloor\end{aligned}$$

然后这里我们看出来应该求这个 $f(T)=\sum_{p\in \mathcal{P},p\mid T}\mu(\dfrac{T}{p})$ 的前缀和。

显然我们可以通过线性筛搞出 $\mu$，然后再用埃氏筛乱搞就能把前缀和搞出来。空间够用，不去想杜教筛之类的方法了。

这里搞这个前缀和的复杂度应该是低于线性的。然后线性筛筛 $\mu$ 和质数的复杂度是线性的。所以复杂度应该是 $O(n)$。

不过我现在发现这个 $\pi(n)\sim \dfrac{n}{\ln n}$ 这个东西似乎在 $n\le 10^7$ 的范围内近似效果并不是很好？靠前的素数密度似乎比想象的大。

然后不就是二维数论分块了吗。。。

总的时间复杂度 $O(n+T\sqrt{n})$。

但是被卡常了。筛的时间大概是 800ms 左右，最后二维数论分块的时间用了接近 3.8s！开了 O2 才勉强卡过。。。

代码：

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
#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;

const ll N=1e7,M=7e5;

ll T,n,m,cnt;

ll prime[M+5],s[N+5],mu[N+5];
bool f[N+5];

inline void Init() {
  mu[1]=1;f[1]=1;
  for(ll i=2;i<=N;i++) {
    if(!f[i]) {prime[++cnt]=i;mu[i]=-1;}
    for(ll j=1;j<=cnt&&prime[j]*i<=N;j++) {
      f[i*prime[j]]=1;
      if(i%prime[j]==0) {mu[i*prime[j]]=0;break;}
      mu[i*prime[j]]=-mu[i];
    }
  }
  for(ll i=1;i<=cnt;i++) {
    for(ll j=prime[i],k=1;j<=N;j+=prime[i],k++) {
      s[j]+=mu[k];
    }
  }
  for(ll i=1;i<=N;i++) {s[i]=s[i-1]+s[i];}
}

inline ll read() {
  ll ret=0,f=1;char ch=getchar();
  while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
  while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
  return ret*f;
}

inline void write(ll x) {
  static char buf[22];static ll len=-1;
  if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
  else {putchar(45);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
  while(len>=0) putchar(buf[len--]);
}

inline void writeln(ll x) {write(x);putchar(10);}

int main() {

  Init();

  T=read();

  while(T--) {
    n=read();m=read();
    ll ans=0;
    for(ll i=1,j;i<=n&&i<=m;i=j+1) {
      j=min(n/(n/i),m/(m/i));ans+=(n/i)*(m/i)*(s[j]-s[i-1]);
    }
    writeln(ans);
  }

  return 0;
}