莫比乌斯反演[学习笔记]

先咕着

求
\[\large \sum_{i=1}^{n} \sum_{j=1}^{m}[gcd(i,j)](n<m)\]

显然
\[\large\sum_{d|n}\varphi(d)=n\]

所以

\[\large\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{d|gcd(i,j)}\varphi(d)\]

\[\large=\sum_{d=1}^{n}\varphi(d)*\lfloor\frac{n}{d}\rfloor*\lfloor\frac{m}{d}\rfloor\]

代码大概长这样(?
预处理

   void init(int x) {
    vis[1] = 1 ; mul[1] = 1 ;
    for(int i = 2 ; i <= x ; i ++) {
      if(! vis[i]) {
        mul[i] = -1 ;
        prm[++ cnt] = i ;
      }
      for(int j = 1 ; j <= cnt && i * prm[j] <= x ; j ++) {
        int k = i * prm[j] ;
        vis[k] = true ;
        if(! (i % prm[j])) { break ; }
        else mul[k] = -mul[i] ;
      }
    }
    for(int i = 1 ; i <= x ; i ++) { pre[i] = pre[i - 1] + mul[i] ; }
  }

for(int l = 1 , r = 0 ; l <= min(n , m) ; l = r + 1) {
   r = min(n / (n / l) , m / (m / l)) ;
   ans += 1ll * (n / l) * (m / l) * (sum[r] - sum[l - 1]) ;
}

[POI2007]ZAP-Queries

求 \(\sum_{i=1}^{n}\sum_{i=1}^{m}[gcd(i,j)==d]\)

显然刚开始的套路是

\[\sum_{i=1}^{\lfloor \frac{n}{d}\rfloor}\sum_{i=1}^{\lfloor \frac{m}{d} \rfloor}[gcd(i,j)==1]\]