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 条评论
登录 后参与评论

相关文章

来自专栏chenssy

【死磕【Sharding-jdbc】---EventBus-轻量级进程内事件分发组件

翻译:将事件分派给监听器,并为监听器提供注册自己的方法。EventBus允许组件之间的发布 - 订阅式通信,而不需要组件彼此明确注册(并且因此彼此意识到)。 它...

10120
来自专栏PHP在线

深入理解PHP原理之异常机制

PHP的异常机制的原理是什么? 在PHP每一个可独立执行的op array最后的ZEND_HANDLE_EXCEPTION是用来干什么呢? 让我们从一个问题说起...

410110
来自专栏大内老A

WCF技术剖析之八:ClientBase<T>中对ChannelFactory<T>的缓存机制

和传统的分布式远程调用一样,WCF的服务调用借助于服务代理(Service Proxy)。而ChannelFactory<T>则是服务代理的创建者。WCF采用基...

213100
来自专栏非著名程序员

EventBus3.0 使用及源码解析

叨了个叨 最近因为换工作的一些琐事搞的我一个头两个大,也没怎么去学新东西,实在是有些愧疚。新项目用到了EventBus3.0,原来只是听说EventBus的鼎鼎...

26080
来自专栏技术/开源

UWP开源项目 LLQNotifier 页面间通信利器(移植EventBus)

前言 EventBus是一个Android版本的页面间通信库,这个库让页面间的通信变得十分容易且大幅降低了页面之间的耦合。小弟之前玩Android的时候就用得十...

21070
来自专栏刘望舒

Android事件总线(二)EventBus3.0源码解析

前言 上一篇我们讲到了EventBus3.0的用法,这一篇我们来讲一下EventBus3.0的源码以及它的利与弊。 1.构造函数 当我们要调用EventBus的...

25650
来自专栏JetpropelledSnake

SNMP学习笔记之SNMP4J介绍(Java)

  SNMP4J是一个用Java来实现SNMP(简单网络管理协议)协议的开源项目.它支持以命令行的形式进行管理与响应。SNMP4J是纯面向对象设计与SNMP++...

39750
来自专栏Java架构沉思录

你真的懂Mybatis缓存机制吗

Mybatis的一级缓存是指Session缓存。一级缓存的作用域默认是一个SqlSession。Mybatis默认开启一级缓存。 也就是在同一个SqlSessi...

1.9K50
来自专栏大内老A

Enterprise Library深入解析与灵活应用(2): 通过SqlDependency实现Cache和Database的同步

对于一个真正的企业级的应用来说,Caching肯定是一个不得不考虑的因素,合理、有效地利用Caching对于增强应用的Performance(减少对基于Pers...

24070
来自专栏林德熙的博客

win10 UWP 显示地图

第一步引用地图xmlns:Map="using:Windows.UI.Xaml.Controls.Maps"

13110

扫码关注云+社区

领取腾讯云代金券