首页 > 代码库 > Codeforces 484(#276 Div 1) B Maximum Value 筛法

Codeforces 484(#276 Div 1) B Maximum Value 筛法

题意:给你一个数组,问你其中 对于  1 <= i,j <= n  ai > aj  中  ai % aj 的最大值是多少

解题思路:筛法求每个数的倍数 ,并找到数组中存在的在它左边离这个倍数最近的树(可以预处理出来)

解题代码:

 1 // Author: darkdream 2 // Created Time: 2014年11月06日 星期四 00时24分10秒 3  4 #include<vector> 5 #include<list> 6 #include<map> 7 #include<set> 8 #include<deque> 9 #include<stack>10 #include<bitset>11 #include<algorithm>12 #include<functional>13 #include<numeric>14 #include<utility>15 #include<sstream>16 #include<iostream>17 #include<iomanip>18 #include<cstdio>19 #include<cmath>20 #include<cstdlib>21 #include<cstring>22 #include<ctime>23 #define LL long long24 25 using namespace std;26 int main(){27     int n ;28     LL l , r;29     scanf("%d",&n);30     for(int i = 1;i <= n;i ++)31     {32         LL ans = 0 ; 33         scanf("%I64d %I64d",&l,&r);34         for(int i = 62 ;i >= 0 ;i --)35         {36             if((r&(1ll << i)) != 0 )37             {38                 if((l & (1ll << i)) != 0 )39                 {40                     ans += (1ll << i);41                     r &=  (~(1ll << i));42                     l &=  (~(1ll << i));43                 }else{44                     if((1ll << (i+1))-1 <= r)45                     {46                         ans +=  (1ll << (i+1)) -1;47                     }48                     else ans += (1ll << i ) - 1; 49                     break;50                 }51             }52 53         }54         printf("%I64d\n",ans);55     }56     return 0;57 }
View Code

 

Codeforces 484(#276 Div 1) B Maximum Value 筛法