NOWCODER 2018(思维题)

标签: 数据结构、算法

在这里插入图片描述
在这里插入图片描述

题意:

给出a,b,c,da,b,c,d,问有多少对(x,y)(x[a,b],y[c,d])(x,y)(x∈[a,b],y∈[c,d])使得xyx*y是2018的倍数

思路:

1.2018的倍数可以是2018n2018*n(n为正整数)
num1为区间[a,b][a,b]20182018的倍数的个数,
num1中的任意一个数和区间[c,d]里的数相乘都是2018的倍数,num2同理
ans+=num1(dc+1)+num2(ba+1)num1num2;∴ans+=num1*(d-c+1)+num2*(b-a+1)-num1*num2;
区间[a,b][a,b]里的2018的倍数和区间[c,d][c,d]里的2018的倍数相乘被计算过两次,所以要减去num1num2num1*num2
2.2018的倍数还可以是1009n1009*n(n为2的倍数)
1009的奇数倍,
此时[a,b][a,b]中1009的奇数倍(偶数倍为2018的倍数,已经计算过,所以要减去num1)与[c,d][c,d]中的偶数(这里偶数中的2018的倍数在第一种情况中计算过了,所以要减去num2)相乘都能组成2018的倍数,
[c,d][c,d]中1009的奇数倍和[a,b][a,b]中的偶数相乘同理,相加即可
ans+=(b/1009(a1)/1009num1)(d/2(c1)/2num2)+(b/2(a1)/2num1)(d/1009(c1)/1009num2);∴ans+=(b/1009-(a-1)/1009-num1)*(d/2-(c-1)/2-num2)+(b/2-(a-1)/2-num1)*(d/1009-(c-1)/1009-num2);

AC代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a,b,c,d;
int main() {
	while(cin>>a>>b>>c>>d) {
		ll num1=b/2018-(a-1)/2018,num2=d/2018-(c-1)/2018;
		ll ans=num1*(d-c+1)+num2*(b-a+1)-num1*num2;
		ans+=(b/2-(a-1)/2-num1)*(d/1009-(c-1)/1009-num2)+(b/1009-(a-1)/1009-num1)*(d/2-(c-1)/2-num2);
		cout<<ans<<endl;
	}
}
版权声明:本文为cat_hate_fish原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/cat_hate_fish/article/details/108079959

智能推荐

bireme数据源同步工具--debezium+kafka+bireme

1、介绍 Bireme 是一个 Greenplum / HashData 数据仓库的增量同步工具。目前支持 MySQL、PostgreSQL 和 MongoDB 数据源 官方介绍文档:https://github.com/HashDataInc/bireme/blob/master/README_zh-cn.md 1、数据流 Bireme 采用 DELETE + COPY 的方式,将数据源的修改记...

一致性hash算法

散列(hash)在我看来就是一个数组,而与数组不同的点在于数组是按顺序写入的,而hash是按照一定的hash算法确定元素在数组中的位置的。hash最难的问题在于会有冲突出现,如果两个object根据相应的hash算法得出的值一样便产生了hash冲突。在所有解决hash冲突的方法中,我最欣赏的是链式解决法,即将hash到同一位置的元素用链表连接。当然还有其它几种处理hash冲突的算法,比如建立公共溢...

OpenCV-Python learning-1.安装,图片读取显示

1. OpenCV与OpenGL区别 https://www.zhihu.com/question/20212016 一个是让机器识别东西的,OpenCV是给电脑做眼睛的。 一个是让机器计算出更好画面的,OpenGL用在游戏渲染方面很多。 OpenCV(Open Source Computer Vision Library)是一个基于(开源)发行的跨平台计算机视觉库,OpenGL(全写Open G...

Mycat+Mysql分布式架构改造和性能压力测试

架构实现 Mycat作为数据库高可用中间件具备很多的功能,如负载均衡,分库分表,读写分离,故障迁移等。结合项目的实际情况,分库分表功能对于关联查询有很高的要求,需要从业务角度考虑分库分表后的关联查询SQL的分析,业务代码动作较大,所以在此方案中我们不考虑分库分表。主要应用Mycat的负载均衡及故障迁移的功能即可。 整个架构改造包括两个部分,第一是单例Mysql改为多个Mysql,同时负载均衡,并且...

人脸识别之疲劳检测(二)阈值法、KNN分类和K-means聚类

Table of Contents 1、均值法 2、中值法 3、KNN 4、K-means 结合上一节在获得人眼特征点后需要对睁眼闭眼状态做出判断,方法的选择需要经验结合公平的评价方法,使用大量测试集得到不同方法下的精确度并做出比较: 1、均值法 50帧睁眼数据取均值,得到不同阈值下精确度。 2、中值法 50帧睁眼数据取中值,得到不同阈值下精确度。 3、KNN KNN是一种ML常用分类算法,通过测...

猜你喜欢

CodeForce Tic-Tac-Toe

Two bears are playing tic-tac-toe via mail. It's boring for them to play usual tic-tac-toe game, so they are a playing modified version of this game. Here are its rules. The game is played on the foll...

Python雾里看花-抽象类ABC (abstract base class)

首先认识模块 abc,python中没有提供抽象类与抽象方法,然而提供了内置模块abc来模拟实现抽象类,例如提供泛映射类型的抽象类 abc.MutableMapping 继承abc.MutableMapping构造一个泛映射类型(类似python中的dict) 当然继承abc.Mapping 也可以,毕竟MutableMapping是其子类 dict是python中典型的映射类型数据结构,其接口的...

python 文件操作

2, with open (‘xx.txt’,‘w’,encoding=‘utf-8’) as f: f.write(‘文件内容或对象’)...

【Python基础】使用统计函数绘制简单图形

机器学习算法与自然语言处理出品 @公众号原创专栏作者 冯夏冲 学校 | 哈工大SCIR实验室在读博士生 2.1 函数bar 用于绘制柱状图 2.2 函数barh 用于绘制条形图 2.3 函数hist 用于绘制直方图 直方图与柱状图的区别 函数pie 用于绘制饼图 2.5 函数polor 用于绘制极线图 极线图是在极坐标系上绘出的一种图。在极坐标系中,要确定一个点,需要指明这个点距原点的角...

css:顶部按钮固定,上面内容滑动

这种需求我们平时见到很多的,实现方法也多的参差不齐,下面我说一种简单的。如图: 可以看到只有红线部分滚动,底下按钮是固定的。 代码...