51NOD 1131 覆盖数字的数量 规律+公式

1131 覆盖数字的数量

1. 1.0 秒
2.  
3. 131,072.0 KB
4.  
5. 20 分
6.  
7. 3级题

给出一段从A - B的区间S（A，B为整数），这段区间内的整数可以随便使用任意次。再给出一段从X - Y的区间T，问用区间S中的整数做加法，可以覆盖区间T中多少个不同的整数。

例如：区间S为8 - 10，区间T为3 - 20。在3 - 20中，整数8(8),9(9),10(10),16(8+8),17(8+9),18(9+9),19(9+10),20(10+10)。可以被区间S中的数覆盖，因此输出8。

 收起

输入

第1行：一个数T，表示后面用作输入测试的数的数量。（1 <= T <= 1000)
第2 - T + 1行：每行4个数：A, B , X, Y，中间用空格分隔。(1 <= A < B <= 10^18, 1 <= X < Y <= 10^18)

输出

输出共T行，每行1个数，区间[X,Y]中可以由A-B中的整数相加得到的不同整数的数量。

输入样例

1
8 10 3 20

输出样例

8

我们知道对于[a,b]，可以构造[a,b],[2*a,2*b],[3*a,3*b]........还有一个规律就是如果某处相交，则往后的数都能覆盖，比如[ka,kb][(k+1)a,(k+1)b]  如果kb>=(k+1)a，kb以后的数都能构造。

k=   a/(b-a)

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef long long ll ;
const int N=1e5+7;
int n;
LL a[N];
LL sum=0;
LL solve(ll a,ll b,ll x,ll y)
{//cout<<a<<"    "<<b<<"             "<<x<<" "<<y<<endl;if(b<x) return 0;if(a>y) return 0;if(a<=x&&b<=y&&b>=x){return b-x+1;}if((a>=x&&b<=y)||(a<=x&&b>=y)){return b-a+1;}if(a>=x&&a<=y&&b>=y){return y-a+1;}
}
int main()
{scanf("%d",&n);while(n--){LL a,b,x,y;scanf("%lld%lld%lld%lld",&a,&b,&x,&y);int k=a/(b-a);if(a%(b-a)==0){k++;}LL ans=0;for(int i=1;i<k;i++){ans+=solve(i*a,i*b,x,y);}printf("%lld\n",ans+solve(k*a,y,x,y));}return 0 ;
}