【ACM-2017四川省赛】G . 2017

痛定思痛。 2022-05-24 07:18 173阅读 0赞

## 题目描述 ##

**G. 2017**

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 multiple of 2017.

**Input**

The input contains zero or more test cases and is terminated by end-of-file.  
Each test case contains four integers a, b, c, d.  
• 1 ≤ a ≤ b ≤ 109 , 1 ≤ c ≤ d ≤ 109  
• The number of tests cases does not exceed 104

**Output**

For each case, output an integer which denotes the result.

**Sample Input**

1 2017 1 2016  
1 1000000000 1 1000000000

**Sample Output**

2016  
991324197233775

## 题意分析 ##

从题目描述中可以很轻易的读懂（英语渣 \_ ），就是给定区间 \[ a , b \] , \[ c , d \] ， 然后分别在两个区间中各找一个数 x , y ， 要求 x 属于第一个区间， y 属于第二个区间，并且 x \* y 是2017的倍数。

拿到这道题目的时候其实我是很开心的，毕竟分析了下就有了思路（毕竟大家都说是水题哒）

## 解题分析 ##

首先，2017是一个素数，那么要想 x \* y 是2017的倍数，x , y 必定存在至少一个数是2017的倍数

当选定了一个数，假定是 x , 那么 y 无论何值都满足条件（注意 a b c d 的范围都是1 到1e9）

对于一个区间中，找出2017的倍数，第一种方法是筛法求，其实这种方法效率已经很高了。不过还有更为高效的方法：就 \[ a , b \] 区间来说，令 m = b/2017, n = a/2017 , 很显然，m - n在大多数情况下就能直接得到此区间中2017的倍数有多少个，但是注意，**当 a 也是2017的倍数的时候，应为 m - n + 1** (此点也是一直卡住我的地方，当时想到了会多一个，但是在判断是否 +1 的这个条件的时候，误以为是只要 a/2017不为0时则加1，从而导致WA，心累呀)

由上边得到了 m 和 n 后，我们能够得到 m\*len2(第二个区间的长度)，n\*len1(第一个区间的长度)之和则为所有的可能数，但是在这样的情况下，我们会发现我们有可能会存在多加的情况，**当两个区间有交集并且交集中存在2017的倍数的情况下**，此时我们会多加一定的可能数，那么我们如何去解决这种情况呢?

第一种方法：既然我们已经算出了 m\*len2 + n\*len1， 那么我们只需要减去对应的重复项即可，即查找出两个区间中重复的2017的倍数项的个数 x，那么结果即为 res = m\*len2 + n\*len1 - x\*x  
第二种方法：我们逆向思考，我们需要的是符合条件的，那么是不是总数 - 不符合条件数即可呢？我们想下，题目中的总数即为len1 \* len2 , 不符合条件的即为 (len1 - m) \* (len2 - n) ，那么结果 res = len1 \* len2 - (len1 - m) \* (len2 - n)

## AC代码 ##

#include <bits/stdc++.h>
    using namespace std;
    int main(){
        long long a,b,c,d;
        while(cin>>a>>b>>c>>d){
            long long len1 = b-a+1;
            long long len2 = d-c+1;
            long long m= 0 ,n=0;
            m = b/2017 - a/2017;
            if(a%2017 == 0){
                m++;
            }
            n = d/2017 - c/2017;
            if(c%2017 == 0){
                n++;
            }
            unsigned long long res = 0;
            res = len1*len2 - (len1-m)*(len2-n);
            cout<<res<<endl;
        }
        return 0;
    }

**注：**

如有错误，欢迎dalao评论指正  
.