做题感悟：这题不难，是一个构造题，找一下规律就好。
解题思路：
假如两个数的二进制位数分别是 a ,b.(这里假设 a < b) , 当 b - a >= 1 时只有两种情况可以选择 (1 << b) - 1 or (1<<a) -1 ,这里当然先判断前一个是否满足,当 a = b 的时候，枚举两个数的每一位，如果出现小的数当前位为 0 ,且大的数当前位为 1 ,那么也有两种情况选择要么当前位加上后面的所有位都为 1 ，要么后面的位全为 1 ，这里也先判断前一种情况。开始的时候要特判一下两个数相等的情况。注意：（1<<b）的时候
1 要替换成 __int64 的变量。
代码：
#include<iostream>
#include<sstream>
#include<map>
#include<cmath>
#include<fstream>
#include<queue>
#include<vector>
#include<sstream>
#include<cstring>
#include<cstdio>
#include<stack>
#include<bitset>
#include<ctime>
#include<string>
#include<cctype>
#include<iomanip>
#include<algorithm>
using namespace std ;
#define INT __int64
#define L(x) (x * 2)
#define R(x) (x * 2 + 1)
const int INF = 0x3f3f3f3f ;
const double esp = 0.0000000001 ;
const double PI = acos(-1.0) ;
const int mod = 1000000007 ;
const int MY = (1<<5) + 5 ;
const int MX = 200000 + 5 ;
const int S = 20 ;
INT Le ,Rt ;
INT judge(INT S)
{
if(!S) return 1 ;
INT temp = 1 ;
for(INT i = 63 ;i >= 0 ; --i)
if(S&(temp<<i))
return i+temp ;
}
int main()
{
INT Tx ,a1 ,a2 ;
scanf("%I64d" ,&Tx) ;
while(Tx--)
{
scanf("%I64d%I64d" ,&Le ,&Rt) ;
a1 = judge(Le) ;
a2 = judge(Rt) ;
if(Le == Rt)
{
cout<<Le<<endl ;
continue ;
}
INT tx ,temp ,A = 1 ;
if(a2 == a1)
{
temp = 0 ;
for(INT i = a1-A ;i >= 0 ; --i)
{
if(!(Le&(A<<i)) && (Rt&(A<<i)))
{
tx = temp ;
tx += (A<<(i+1)) - A ;
if(tx >= Le && tx <= Rt)
cout<<tx<<endl ;
else
{
temp += (A<<i) -A ;
cout<<temp<<endl ;
}
break ;
}
if(Le&(A<<i)) temp += (A<<i) ;
}
}
else
{
INT temp = (A<<a2) - A ;
if(temp > Rt)
cout<<((A<<(a2-A))-A)<<endl ;
else cout<<temp<<endl ;
}
}
return 0 ;
}
做题感悟：这题真没向二分方向考虑，只考虑到与倍数相差尽量小，二分大法好！
解题思路：
方法一 、 如果要使 a [ i ] % a [ j ] 尽量大，我们可以找 小于 k * a[ j ] 且最接近这个数的数，那么对 a [ j ] 取模与其它数相比一定更优。优化：从大到小枚举，这样每次判断最优值，如果a [ j ] - 1 不大于最优解就 break ；
方法二、类似筛法的思想，其实和第一种差不多，都是找最接近 k * a [ j ] 的数，具体见代码。
代码：
#include<iostream>
#include<sstream>
#include<map>
#include<cmath>
#include<fstream>
#include<queue>
#include<vector>
#include<sstream>
#include<cstring>
#include<cstdio>
#include<stack>
#include<bitset>
#include<ctime>
#include<string>
#include<cctype>
#include<iomanip>
#include<algorithm>
using namespace std ;
#define INT __int64
#define L(x) (x * 2)
#define R(x) (x * 2 + 1)
const int INF = 0x3f3f3f3f ;
const double esp = 0.0000000001 ;
const double PI = acos(-1.0) ;
const int mod = 1000000007 ;
const int MY = (1<<13) + 5 ;
const int MX = 200000 + 5 ;
const int MS = 2000000 ;
int n ;
int g[MX] ;
int main()
{
//freopen("input.txt" ,"r" ,stdin) ;
while(~scanf("%d" ,&n))
{
for(int i = 0 ;i < n ; ++i)
scanf("%d" ,&g[i]) ;
sort(g ,g+n) ;
n = unique(g ,g+n) - g ;
int ans = 0 ;
for(int i = n - 1 ;i >= 0 ; --i)
{
if(ans >= g[i]-1) break ;
for(int j = 2 ; ; ++j)
{
int mx = lower_bound(g ,g+n ,g[i]*j) - g ;
ans = max(ans ,(g[mx-1])%g[i]) ;
if(mx >= n) break ;
}
}
printf("%d\n" ,ans) ;
}
return 0 ;
}
代码：
#include<iostream>
#include<sstream>
#include<map>
#include<cmath>
#include<fstream>
#include<queue>
#include<vector>
#include<sstream>
#include<cstring>
#include<cstdio>
#include<stack>
#include<bitset>
#include<ctime>
#include<string>
#include<cctype>
#include<iomanip>
#include<algorithm>
using namespace std ;
#define INT __int64
#define L(x) (x * 2)
#define R(x) (x * 2 + 1)
const int INF = 0x3f3f3f3f ;
const double esp = 0.0000000001 ;
const double PI = acos(-1.0) ;
const int mod = 1000000007 ;
const int MY = (1<<13) + 5 ;
const int MX = 200000 + 5 ;
const int MS = 2000000 ;
int n ;
int g[MS] ;
int main()
{
int x ;
while(~scanf("%d" ,&n))
{
g[0] = 1 ;
for(int i = 0 ;i < n ; ++i)
{
scanf("%d" ,&x) ;
g[x] = x ;
}
for(int i = 1 ;i <= MS ; ++i)
if(g[i] != i)
g[i] = g[i-1] ;
int ans = 0 ;
for(int i = 1 ;i <= MS ; ++i)
if(g[i] == i)
{
for(int j = i*2 ;j <= MS ; j = j+i)
ans = max(ans ,g[j-1]%i) ;
}
cout<<ans<<endl ;
}
return 0 ;
}