Summit Online Judge

题意：

询问将取值在 $[L,R]$ 的若干个整数相加，可以得到 $[x,y]$ 区间内多少个数字。

解法：

只需要考虑求 $[L,R]$ 的数字能凑出 $[1,n]$ 的多少个数字，即可得出答案。

考虑 $[1,n]$ 的数字 $i$

　　1.对于 $i < L$，显然无法凑出。

　　2.当 $i > L$ 时，$[L,R]$可以凑出的数字的集合是区间 $[L,R]$, $[2L,2R]$, $[3L,3R]$, $[4L,4R]$ ... $[tL,tR]$ 的并

　　注意到当$[nL,nR]$和$[(n+1)L,(n+1)R]$ 相交时，$[nL,+∞)$都可以凑出。

　　所以答案是一些大小呈等差数列的独立集合与末位的一堆数字的并，分类计算即可。

总效率$O(1)$

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 
 5 #define LL long long
 6 
 7 using namespace std;
 8 
 9 LL A,B,X,Y;
10 
11 LL Sum(LL n)
12 {
13     if(n%2==0) return n/2*(n+1);
14     else return (n+1)/2*n;
15 }
16 
17 LL calc(LL n)
18 {
19     if(n<A) return 0LL;
20     LL t = A/(B-A);
21     LL x = n/A;
22     LL ans=0;
23     if(x<=t)
24     {
25         ans += n-x*A+1;
26         ans += Sum(x-1)*(B-A+1);
27     }
28     else
29     {
30         ans += n-t*A+1;
31         ans += Sum(t-1)*(B-A+1);
32     }
33     return ans;
34 }
35 
36 int main()
37 {
38     int T;
39     cin>>T;
40     while(T--)
41     {
42         cin>>A>>B>>X>>Y;
43         X = max(X,A);
44         if(X>Y)
45         {
46             puts("0");
47             continue;
48         }
49         else if(Y<=B)
50         {
51             cout<<Y-X+1<<endl;
52             continue;
53         }
54         LL ans=calc(Y)-calc(X-1);
55         cout << ans << endl;
56     }
57     return 0;
58 }

View Code