2018 湖南网络比赛题 HDU - 6286 (容斥)

时间:2023-03-10 01:53:10
2018  湖南网络比赛题  HDU - 6286  (容斥)

题意:不说了。

更加偏向于数学不好的小可爱来理解的。

这篇博客更加偏重于容斥的讲解。用最直观的数学方法介绍这个题。

思路:

在a<=x<=b. c<=y<=d 中满足  x*y%2018=0.  其实,2018的质因子为 2, 1009。 好吧,那么关于2018的倍数都可以表示为  2k*1009*u.   那么要找有多少(x, y)有多少对。(例如:(1,2018)和(2018, 1)是两组).

设倍数为  w=2k*1009*u.   那么也就是 {(x, y)|  x=2k , y=1009u  }  和 { (x, y)| x=1009k, y=2u  }的方案数。

在这里我先放一张图:

2018  湖南网络比赛题  HDU - 6286  (容斥)

由w=2k*1009*u和 图得, A= {x*y%2018==0事件};A就是1009倍数事件并上2的倍数。

主要思路就是,先求,{右边区域或者左边至少有一个2018的倍数和2018}  的方案数。

2018  湖南网络比赛题  HDU - 6286  (容斥)然后求 2018  湖南网络比赛题  HDU - 6286  (容斥)  就没了。

好了:ac代码如下:

#include<iostream>
using namespace std;
#define ll long long
int main()
{
ll a, b, c, d;
while (cin >> a >> b >> c >> d)
{
ll ans = ;
ll k2018 = b / - a / ; ll u2018 = d / - c / ;    //求2018的倍数的个数
if (a % == ) ++k2018; if (c % == ) ++u2018;    //这里注意一下为什么这么写
ll k1009 = b / - a / ; ll u1009 = d / - c / ;    //求1009的倍数(包括了2018的倍数)
if (a % == )++k1009; if (c % == )++u1009;
ll k2 = b / - a / ; ll u2 = d / - c / ;               //求2的倍数
if (a % == )++k2; if (c % == )++u2;
k1009 -= k2018; u1009 -= u2018; k2 -= k2018; u2 -= u2018;//求1009的倍数并且不包括2018的倍数,2的倍数并且不包括2018的倍数
ans = k2018*(d - c + ) + u2018*(b - a + )-k2018*u2018;      //这里注意一下,因为(1,1)和(1,1)是相同的   
ans += k1009*u2 + u1009*k2;  
cout << ans << endl;
}
}