HDU-1695-GCD

ACM模版

描述

题解

莫比乌斯反演入门题,给大家推荐一个写的十分详细的博客,由浅入深,大赞!__proto__’s blog,让我更加清晰的认识了莫比乌斯反演的用处,感谢大佬!

代码

#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

const int MAXN = 1e5 + 7;

int a, b, c, d, k, cnt;
int pri[MAXN];
int miu[MAXN];
bool vis[MAXN];

void init()
{
    memset(pri, 0, sizeof(pri));
    memset(miu, 0, sizeof(miu));
    memset(vis, 0, sizeof(vis));
    miu[1] = 1;
    cnt = 0;
    for (int i = 2; i < MAXN; i++)
    {
        if (!vis[i])
        {
            pri[cnt++] = i;
            miu[i] = -1;
        }
        for (int j = 0; j < cnt && i * pri[j] < MAXN; j++)
        {
            vis[i * pri[j]] = 1;
            if (i % pri[j])
            {
                miu[i * pri[j]] = -miu[i];
            }
            else
            {
                miu[i * pri[j]] = 0;
                break;
            }
        }
    }
}

int main()
{
    init();

    int T;
    cin >> T;
    for (int i = 1; i <= T; i++)
    {
        printf("Case %d: ", i);
        scanf("%d%d%d%d%d", &a, &b, &c, &d, &k);

        if (k == 0)
        {
            puts("0");
            continue;
        }

        b /= k;
        d /= k;
        int t = min(b, d);
        long long ans1 = 0, ans2 = 0;
        for (int i = 1; i <= t; i++)
        {
            ans1 += (long long)miu[i] * (b / i) * (d / i);
        }
        for (int i = 1; i <= t; i++)
        {
            ans2 += (long long)miu[i] * (t / i) * (t / i);
        }

        printf("%lld\n", ans1 - (ans2 >> 1));
    }

    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • hdu 1695 GCD(莫比乌斯反演)

    GCD Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/...

    Gxjun
  • HDU 1695 GCD (欧拉函数,容斥原理)

    GCD Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java...

    ShenduCC
  • hdu----149850 years, 50 colors(最小覆盖点)

    50 years, 50 colors Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 3276...

    Gxjun
  • 数论-GCD、LCM、扩展欧几里得

    给定若干区间的GCD,试还原原数组。 贪心乘最小的数使得区间内每个数是ans[i]的倍数(LCM),最后再检查一遍。

    唔仄lo咚锵
  • 数论-同余与逆元

    将一个数拆成若干数,求其乘积最大。 先上结论:一个数n拆成m个数使其乘积最大,则拆成m个n/m;如果nm不整除则拆成一段连续自然数(从2开始,剩下的往前摊);...

    唔仄lo咚锵
  • HDU-2588-GCD

    ACM模版 描述 ? 题解 image.png 代码 #include <stdio.h> #include <math.h> int Euler(int n...

    f_zyj
  • HDU 1014 Uniform Generator【GCD,水】

    Uniform Generator Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/...

    Angel_Kitty
  • 数学--数论--HDU 5223 - GCD

    Describtion In mathematics, the greatest common divisor (gcd) of two or more in...

    风骨散人Chiam
  • 数学--数论--HDU 4675 GCD of Sequence

    风骨散人Chiam

扫码关注云+社区

领取腾讯云代金券