2018(容斥定理 HDU6286)

2018

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 507 Accepted Submission(s): 263

Problem Description

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

1 2 1 2018

1 2018 1 2018

1 1000000000 1 1000000000

Sample Output

6051

1485883320325200

思路：

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代码：

#include<stdio.h>

#include<iostream>

#include<string.h>

#include<algorithm>

#include<math.h>

#include<string>

#include<queue>

#include<utility>

#define ll long long

using namespace std;

const int maxn = 1e5+;

int main(int argc, char const *argv[])

{

    ll a,b,c,d;

    while(~scanf("%lld %lld %lld %lld",&a,&b,&c,&d))

    {

        ll s1 = b-a+;

        ll s2 = d-c+;

        ll s1_odd = b/-(a-)/;

        ll s1_1009 = b/-(a-)/;

        ll x1=(b/-(a-)/)*s2;

        ll x2=(s1_odd-(b/-(a-)/))*(d/-(c-)/);

        ll x3=(s1_1009-(b/-(a-)/))*(d/-(c-)/);

        ll x4=((s1-s1_odd)-(s1_1009-(b/-(a-)/)))*(d/-(c-)/);

        printf("%lld\n",x1+x2+x3+x4);

    }

    return ;

}

巴特西

2018(容斥定理 HDU6286)

最新文章

热门文章