本文共 2455 字，大约阅读时间需要 8 分钟。

莫比乌斯反演

令F(n)和f(n)都是定义在非负整数域上的两个函数，并且它们之间满足：

const int N = 5000005;bool vis[N];int mob[N], prime[N];int tot;//用来记录prime的个数void Mobius(int n) {
      //求得莫比乌斯函数值    memset(prime, 0, sizeof(prime));    memset(mob, 0, sizeof(mob));    memset(vis, 0, sizeof(vis));    tot = 0, mob[1] = 1;    for (int i = 2; i <= n; i++) {
           if (!vis[i]) {
               prime[tot++] = i;            mob[i] = -1;        }        for (int j = 0; j < tot && i * prime[j] <= n; j++) {
               vis[i * prime[j]] = 1;            if (i % prime[j]) mob[i * prime[j]] = -mob[i];            else {
                   mob[i * prime[j]] = 0;                break;            }        }    }}

1180 方格射击游戏

题目

M*N的方格矩阵，一个人在左下角格子的中心，除他所站位置外，其他格子的中心都有一个敌人，他一次可发射一枚子弹干掉一条直线上的所有敌人，问至少要发射多少子弹才能干掉所有敌人。

输入

输入2个数m, n，中间用空格分隔，对应矩阵的大小。(1 <= m,n <= 5 * 10^6)

输出

输出发射子弹的数量。

输入样例

2 10

输出样例

11

代码

#include 
   
    using namespace std;typedef long long ll;const int N = 5000005;int mob[N], vis[N], prime[N], sum[N];int tot;//用来记录prime的个数void Mobius(int n) {
      //求得莫比乌斯函数值    memset(prime, 0, sizeof(prime));    memset(mob, 0, sizeof(mob));    memset(vis, 0, sizeof(vis));    tot = 0, mob[1] = 1;    for (int i = 2; i <= n; i++) {
           if (!vis[i]) {
               prime[tot++] = i;            mob[i] = -1;        }        for (int j = 0; j < tot && i * prime[j] <= n; j++) {
               vis[i * prime[j]] = 1;            if (i % prime[j]) mob[i * prime[j]] = -mob[i];            else {
                   mob[i * prime[j]] = 0;                break;            }        }    }    for (int i = 1; i <= n; ++i) {
           sum[i] = sum[i - 1] + mob[i];    }}int main() {
       Mobius(N - 1);    int n, m;    scanf("%d%d", &n, &m);    if (n == 1 && m == 1) puts("0");    else if (n == 1 || m == 1) puts("1");    else {
           --n;        --m;        if (n > m) swap(n, m);        ll ans = 2;        for (int L = 1, R; L <= n; L = R + 1) {
               R = min(n / (n / L), m / (m / L));            ans += (ll) (sum[R] - sum[L - 1]) * (ll) (n / L) * (ll) (m / L);        }        printf("%lld\n", ans);    }    return 0;}
   

转载地址：https://blog.csdn.net/weixin_43820352/article/details/108246485 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！