前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布

K.2018

作者头像
Cell
发布2022-02-24 17:42:21
1420
发布2022-02-24 17:42:21
举报
文章被收录于专栏:Cell的前端专栏Cell的前端专栏

K. 2018

Given a,b,c,d, find out the number of pairs of integers (x,y) where a ≤ x ≤ b,c ≤ y ≤ d and x·y is a multiple of 2018.

Input

The input consists of several test cases and is terminated by end-of-file. Each test case contains four integers a,b,c,d.

Output

For each test case, print an integer which denotes the result.

Constraint

• 1≤ a ≤ b ≤109,1≤ c ≤ d ≤109 • The number of tests cases does not exceed 104.

Sample Input

代码语言:javascript
复制
1 2 1 2018
1 2018 1 2018
1 1000000000 1 1000000000

Sample Output

代码语言:javascript
复制
3
6051
1485883320325200

题意:给定区间 [a,b]、[c,d],问有多少对有序数组 (x,y)(x∈[a,b],y∈[c,d]) 使得 xy 是 2018 的倍数 思路:2018=21009(分解质因数),则对 x 分类讨论:1) 仅为 2 的倍数;2)仅为 1009 的倍数;3)即为 2 又为 1009 的倍数;4)既不为 2 又不为 1009 的倍数 等价于如下分类讨论:

  1. 若 x 是偶数:1)若 x 是 1009 的倍数,则 y 可为 [c,d] 中任意数; 2)若 x 不是 1009 的倍数,则 y 必定为 [c,d] 中 1009 的倍数
  2. 若 x 是奇数:1)若 x 是 1009 的倍数,则 y 必定为 [c,d] 中 2 的倍数; 2)若 x 不是 1009 的倍数,则 y 必定为 [c,d] 中 2018 的倍数

后 AC 代码

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

#include<cstdio> #include<iostream> typedef unsigned long long ll; using namespace std; int main(){ ll a,b,c,d; while(cin>>a>>b>>c>>d){ ll num1_all_1009=b/1009-(a-1)/1009; ll num1_even=b/2-(a-1)/2; ll num1_1009_in_even=b/2018-(a-1)/2018; ll num1_rest_in_even=num1_even-num1_1009_in_even; ll num1_odd=(b-a+1)-num1_even; ll num1_1009_in_odd=num1_all_1009-num1_1009_in_even; ll num1_rest_in_odd=num1_odd-num1_1009_in_odd; ll ans=0; ans+=num1_1009_in_even*(d-c+1); ll num2_all_1009=d/1009-(c-1)/1009; ans+=num1_rest_in_even*num2_all_1009; ll num2_even=d/2-(c-1)/2; ans+=num1_1009_in_odd*num2_even; ll num2_all_2018=d/2018-(c-1)/2018; ans+=num1_rest_in_odd*num2_all_2018; cout<<ans<<endl; } return 0; }

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2018-06-14,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • K. 2018
    • Input
      • Output
        • Constraint
          • Sample Input
            • Sample Output
            领券
            问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档