题意:不说了。
更加偏向于数学不好的小可爱来理解的。
这篇博客更加偏重于容斥的讲解。用最直观的数学方法介绍这个题。
思路:
在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 }的方案数。
在这里我先放一张图:
由w=2k*1009*u和 图得, A= {x*y%2018==0事件};A就是1009倍数事件并上2的倍数。
主要思路就是,先求,{右边区域或者左边至少有一个2018的倍数和2018} 的方案数。
然后求
就没了。
好了: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;
}
}