莫比乌斯反演学习

未完成，题量有限。

莫比乌斯入门（牛客）

题意
给两个正整数a，b，求分别在a和b范围内gcd(x, y) = d的整数对有多少个。

思路
公式求范围内gcd(x, y) = d 等价于根据公式将范围和d同时除以d。
此外连同莫比乌斯函数求和即可。
如何实现？ 数论分块+前缀和

代码

int tt, a, b, d, tot, ans;
int miu[N], prim[M], vis[N];

int main() {
   miu[1] = 1;
   for(int i = 2; i <= N; ++i) {
      if(!vis[i]) prim[++tot] = i, miu[i] = -1;
      for(int j = 1; j <= tot && prim[j] * i <= N; ++j) {
         int tmp = i * prim[j];
         vis[tmp] = 1;
         miu[tmp] = i%prim[j] ? -miu[i] : 0;
         if(i % prim[j] == 0) break;
      }
   }
   for(int i = 1; i <= N; ++i) miu[i] += miu[i-1];
   for(cin >> tt; tt--; ) {
      ans = 0;
      scanf("%d %d %d", &a, &b, &d);
      a /= d, b /= d;
      if(a > b) swap(a, b);
      for(int i = 1; i <= a; ) {
         int j = min(a / (a / i), b / (b / i));
         ans += (a/i) * (b/i) * (miu[j] - miu[i-1]);
         i = j+1;
      }
      cout<<ans<<endl;
   }
}

HDU-6363

ll F[M], invF[M];
ll power(ll a, ll b) {
    ll ret = 1;
    while(b) {
        if(b & 1) ret = (ret * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return ret;
}
void initc() {
    F[0] = 1;
    for(int i = 1; i < M; i++) {
        F[i] = (F[i - 1] * i) % mod;
    }
    invF[M - 1] = power(F[M - 1], mod - 2);
    for(int i = M - 2; i >= 0; i--) {
        invF[i] = invF[i + 1] * (i + 1) % mod; //invF[i]*i!=1,invF[i+1]*i!*(i+1)=1
    }
}
// 求组合数
ll C(int n, int m) {
    if(n < 0 || m < 0 || m > n) return 0;
    if(m == 0 || m == n)    return 1;
    return F[n] * invF[n - m] % mod * invF[m] % mod;
}
int prime[M], mob[M], p[M];

void init() {
    int pnum = 0;
    memset (prime, true, sizeof (prime) );
    mob[1] = 1;
    for (int i = 2; i < M; i++) {
        if (prime[i]) {
            p[pnum ++] = i;
            mob[i] = -1;
        }
        for (int j = 0; j < pnum && (ll) i * p[j] < M; j++) {
            prime[i * p[j]] = false;
            if (i % p[j] == 0) {
                mob[i * p[j]] = 0;
                break;
            }
            mob[i * p[j]] = -mob[i];
        }
    }
}
ll fob[M];
int main() {
    fob[0] = 0; fob[1] = 1;
    for(int i = 2; i < M; ++i) fob[i] = (fob[i - 1] + fob[i - 2]) % mod;
    init(); initc();
    int T;
    //FIN;
    cin >> T;
    while(T--) {
        int n, k; scanf("%d%d", &n, &k);
        ll ans = 0;
        for1(i, n) {
            if(n % i) continue;
            ll t = 0;
            for(int j = i; j <= n; j += i)
                if(n % j == 0) t = (t + mob[j / i] * C(n / j + k - 1, k - 1) + mod) % mod;
            ans = (ans + t * (power(2ll, fob[i]) - 1 + mod)) % mod;
        }
        ll dx = C(n + k - 1, k - 1);
        dx = power(dx, (ll)mod - 2);
        printf("%lld\n", ans * dx % mod);
    }
    return 0;
}