链接：/acm/contest/1107/K
来源：牛客国庆集训派对day2
题目描述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 .输入描述
The input consists of several test cases and is terminated by end-of-file.
Each test case contains four integers a, b, c, d.输出描述
For each test case, print an integer which denotes the result.输入
1 2 1
1 1
1 1000000000 1 1000000000输出
3
6051
1485883320325200备注
1 ≤ a ≤ b ≤ 109,1 ≤ c ≤ d ≤ 109
The number of tests cases does not exceed 104.
题意：给两个区间，这两个区间内分别取一个数使得这两个数的乘积是 的倍数。
思路： 的因子有 1，2，1009，。我们将这些因子互相配对。
(1k，k)
(2k，1009k)
(1009k，2k)
(k，1k)
其中存在重复的对数
(2k，k)
(1009k，k)：这两个重复删除了一次(k，k)
(k，k)
(k，2k)
(k，1009k)：这两个重复删除了一次(k，k)
对于因子的个数容斥的方法来求即可。
#include<bits/stdc++.h>using namespace std;typedef long long ll;const int Max_n = 1e6 + 10;int main() {int l1, r1, l2, r2;while(~scanf("%d%d%d%d", &l1, &r1, &l2, &r2)) {int cnt1_1 = r1 - (l1 - 1), cnt1_2 = r1 / 2 - (l1 - 1) / 2;int cnt1_1009 = r1 / 1009 - (l1 - 1) / 1009, cnt1_ = r1 / - (l1 - 1) / ;//cout<<cnt1_1<<" "<<cnt1_2<<" "<<cnt1_1009<<" "<<cnt1_<<endl;int cnt2_1 = r2 - (l2 - 1), cnt2_2 = r2 / 2 - (l2 - 1) / 2;int cnt2_1009 = r2 / 1009 - (l2 - 1) / 1009, cnt2_ = r2 / - (l2 - 1) / ;//cout<<cnt2_1<<" "<<cnt2_2<<" "<<cnt2_1009<<" "<<cnt2_<<endl;ll ans = (ll)cnt1_1 * (ll)cnt2_ + (ll)cnt1_2 * (ll)cnt2_1009 + (ll)cnt1_1009 * (ll)cnt2_2 +(ll)cnt1_ * (ll)cnt2_1;ans -= ((ll)cnt1_2 + (ll)cnt1_1009) * (ll)cnt2_;ans -= ((ll)cnt2_2 + (ll)cnt2_1009) * (ll)cnt1_;//ans+=(ll)cnt1_*(ll)cnt2_;//ans-=(ll)cnt1_1009*(ll)cnt2_;//ans-=(ll)(cnt1_)*(ll)cnt2_1009;ans += (ll)cnt1_ * (ll)cnt2_;printf("%lld\n", ans);}return 0;}/*** Copyright(c)* All rights reserved.* Author : Max_n* Date : -10-02-14.26.07* Problem : */
