牛客题解-小红的区间查询
链接：https://ac.nowcoder.com/acm/contest/128186/A
来源：牛客网
题目描述
\hspace{15pt}小红拿到了两个整数 a,b(a<b)a,b\left(a < b\right)a,b(a<b)。现在她想知道 [l,r]\left[l,r \right][l,r] 内有多少元素 xxx 满足 x−ax - ax−a 是 x−bx-bx−b 的倍数，请你帮帮她。
输入描述:
\hspace{15pt}每个测试文件均包含多组测试数据。第一行输入一个整数 T(1≦T≦105)T\left(1\leqq T\leqq 10^5\right)T(1≦T≦105) 代表数据组数，每组测试数据描述如下：
\hspace{15pt}第一行输入四个整数 a,b,l,r(1≦a<b≦2×105,b<l≦r≦109)a,b,l,r\left(1\leqq a<b\leqq2\times 10^5,b< l\leqq r\leqq10^9\right)a,b,l,r(1≦a<b≦2×105,b<l≦r≦109)。
输出描述:
\hspace{15pt}对于每组测试数据，新起一行。输出一个整数，代表区间内符合条件的元素的数量。示例1
输入
复制3 1 2 3 4 1 5 6 10 114 514 515 1000000000
3 1 2 3 4 1 5 6 10 114 514 515 1000000000
输出
复制1 3 15
1 3 15
说明
对于第一组数据，符合条件的元素仅有 333。
对于第二组数据，符合条件的元素有 6,7,96,7,96,7,9。
问题分析
条件：(x−a)%(x−b)==0
设 k=x−b ，则 x−a=k+(b−a)
条件变为：(k+(b−a))%k==0 ，即 (b−a)%k==0
所以 k 必须是 (b−a) 的约数，且 k=x−b>0 （因为 x>b ，由 b<l≤x 保证）
因此：x=b+d ，其中 d 是 (b−a) 的正约数
////暴力枚举(TLE) //#include <bits/stdc++.h> //using namespace std; //typedef long long ll; // //int main() //{ // ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); // int t; // cin >> t; // while(t--) // { // ll a, b, r, l, x, sum=0; // cin >> a >> b >> l >> r; // x = l; // while(x <= r) // { // if((x-a) % (x-b) == 0) // { // sum++; // //cout << "x =" << x << '\n'; // } // x++; // } // cout << sum <<'\n'; // } //} #include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t; cin >> t; while(t--) { ll a, b, l, r; cin >> a >> b >> l >> r; ll diff = b - a; ll sum = 0; for(ll i = 1; i * i <= diff; i++) { if(diff % i == 0) { ll x1 = b + i; if(x1 >= l && x1 <= r) sum++; if(i * i != diff) { ll x2 = b + diff / i; if(x2 >= l && x2 <= r) sum++; } } } cout << sum << '\n'; } }注意:
(b-a) % k = 0 -> b-a = n(x-b) -> x = (b-a)/n + b
n 有两个解:
小的那个 n1 ≤√diff
大的那个 n2 ≥√diff