链接https://ac.nowcoder.com/acm/contest/128186/A来源牛客网题目描述\hspace{15pt}小红拿到了两个整数 a,b(ab)a,b\left(a b\right)a,b(ab)。现在她想知道 [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≦ab≦2×105,bl≦r≦109)a,b,l,r\left(1\leqq ab\leqq2\times 10^5,b l\leqq r\leqq10^9\right)a,b,l,r(1≦ab≦2×105,bl≦r≦109)。输出描述:\hspace{15pt}对于每组测试数据新起一行。输出一个整数代表区间内符合条件的元素的数量。示例1输入复制3 1 2 3 4 1 5 6 10 114 514 515 10000000003 1 2 3 4 1 5 6 10 114 514 515 1000000000输出复制1 3 151 3 15说明对于第一组数据符合条件的元素仅有 333。对于第二组数据符合条件的元素有 6,7,96,7,96,7,9。问题分析条件(x−a)%(x−b)0设 kx−b 则 x−ak(b−a)条件变为(k(b−a))%k0 即 (b−a)%k0所以 k 必须是 (b−a) 的约数且 kx−b0 因为 xb 由 bl≤x 保证因此xbd 其中 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, sum0; // 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 bn 有两个解:小的那个 n1 ≤√diff大的那个 n2 ≥√diff