51nod 1131 数列

2024-02-04 18:20

文章标签 数列 51nod 1131

本文主要是介绍51nod 1131 数列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1131

1131 覆盖数字的数量

基准时间限制：1 秒空间限制：131072 KB 分值: 80 难度：5级算法题

关注

给出一段从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。

Input

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

Output

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

Input示例

1
8 10 3 20

Output示例

8
  首先要知道，[A,B]所能覆盖的区间是[k*A,k*B],这段区间一直往下走的话总会出现第一次重叠的地方，这时k*A之后的所有数字都可以表示出来了，因为所有的区间都将出现重叠。
证明如下，假设第一次出现重叠是[k*A,k*B],[(k+1)*A,(k+1)*B], 那么有k*A+A<=k*B,  ==> k*A+A*2<=k*B+A<=k*B+B  ==>  (k+2)*A<=(k+1)*B ,  显然之后的区间也会重叠。
然后暴力找找，重复时加一下break就好了。

虽然过了但我感觉还是可以卡的如果想的话，比如这组数据 
100000000(A) 100000001(B) 1000000000000000000(X) 1000000000000000001(Y) 本机要跑300+ms，如果很多组这个的话肯定T了

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define LL  long long
 4 int main()
 5 {
 6     LL A,B,X,Y;
 7     int T,i,j;
 8     cin>>T;
 9     while(T--){
10         LL res=0;
11         scanf("%lld%lld%lld%lld",&A,&B,&X,&Y);
12         for(i=1;;i++)
13         {
14             if(i*A>Y)break;
15             if((i+1)*A<=i*B){
16                 if(i*A<=X) res=Y-X+1;
17                 else res+=Y-i*A+1;
18                 break;
19             }
20             else{
21                 if(i*A>=X&&i*B<=Y) res+=i*B-i*A+1;
22                 else if(i*B>=X) res+=i*B-X+1;
23                 else if(i*A<=Y) res+=Y-i*A+1;
24             }
25         }
26         printf("%lld\n",res);
27     }
28     return 0;
29 }