[2018 江苏省大学生程序设计大赛]

K. 2018 (测试数据范围有扩大)

Problem

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

• Qing Jiang felt that the original edition of the test cases is too easy, so he enlarged the scope of data. The current edition is:

• 1 ≤ a ≤ b ≤ 2³¹ - 1, 1 ≤ c ≤ d ≤ 2³¹ - 1

• The number of tests cases is around at 1·10⁵.

Sample Input

1 2 1 2018

1 2018 1 2018

1 1000000000 1 1000000000

Sample Output

Constraint of original edition (省赛原题测试数据规模，非 TSOJ 此题的数据规模，下列数据 仅供参考 )

• 1 ≤ a ≤ b ≤ 10⁹, 1 ≤ c ≤ d ≤ 10⁹

• The number of tests cases does not exceed 10⁴.

题目大意： 在a，b区间和c，d区间内找一些数使得这些数的乘积是2018的倍数

题解   ：   找2018的约数，有1,2,1009,2018这四个数，然后找它们的数量

#include<iostream>

#include<cstdio>

using namespace std;

long long Count(int n,int m) //用来求区间中2的倍数的个数

{

    if(n%==&&m%==)

        return ((m-n)/+);

    else if(n%!=&&m%!=)

        return ((m-n)/);

    else

        return ((m-n+)/);

}

int main()

{

    int a,b,c,d;

    long long ans,f1,f2;

    while(scanf("%d%d%d%d",&a,&b,&c,&d)!=EOF)

    {

        ans=;

        f1=Count(a,b);

        f2=Count(c,d);

        long long a18=d/-(c-)/;//区间中2018的倍数的个数

            ans+=a18*(b-a+);　　

        long long a19=d/-(c-)/-a18;　　//区间中1009的倍数的个数

            ans+=a19*f1;

        long long a28=b/-(a-)/;

            ans+=a28*(d-c+);

        long long a29=b/-(a-)/-a28;

            ans+=a29*f2;

        printf("%lld\n",ans-(a29*a18+a28*(a19+a18)));//最后要减去多乘的数

    }

    return ;

}