51 nod 1421 最大MOD值-白红宇

51 nod 1421 最大MOD值

阅读量：6156 次

发布时间：2019-06-21

本文共 1943 字，大约阅读时间需要 6 分钟。

1421 最大MOD值

题目来源： CodeForces

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

有一个a数组，里面有n个整数。现在要从中找到两个数字(可以是同一个)

Input

单组测试数据。第一行包含一个整数n，表示数组a的大小。(1 ≤ n ≤ 2*10^5)第二行有n个用空格分开的整数ai (1 ≤ ai ≤ 10^6)。

Output

输出一个整数代表最大的mod值。

Input示例

33 4 5

Output示例

/*51 nod 1421 最大MOD值problem:从数组中选择两个数使 a[i]%a[j]最大solve:可以发现a[i]越接近a[j]的倍数则越大. 所以枚举a[j]的倍数然后二分查找.最开始以为这个会T....M+M/2+...M=O(MlgM)hhh-2016/09/16-16:33:10*/#pragma comment(linker,"/STACK:124000000,124000000")#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              #define lson i<<1#define rson i<<1|1#define ll long long#define clr(a,b) memset(a,b,sizeof(a))#define scanfi(a) scanf("%d",&a)#define scanfs(a) scanf("%s",a)#define scanfl(a) scanf("%I64d",&a)#define scanfd(a) scanf("%lf",&a)#define key_val ch[ch[root][1]][0]#define eps 1e-7#define inf 0x3f3f3f3f3f3f3f3fusing namespace std;const ll mod = 1e9+7;const int maxn = 200010;const double PI = acos(-1.0);template
               
                 void read(T&num){ char CH; bool F=false; for(CH=getchar(); CH<'0'||CH>'9'; F= CH=='-',CH=getchar()); for(num=0; CH>='0'&&CH<='9'; num=num*10+CH-'0',CH=getchar()); F && (num=-num);}int stk[70], tp;template
                
                  inline void print(T p){ if(!p) { puts("0"); return; } while(p) stk[++ tp] = p%10, p/=10; while(tp) putchar(stk[tp--] + '0'); putchar('\n');}int a[maxn];int main(){ int n; read(n); for(int i =0; i < n; i++) { read(a[i]); } sort(a,a+n);// int cnt = unique(a,a+n)-a; int ans = 0; for(int i =0; i < n; i++) { if(a[i] == 1) continue; for(int j = 1;j <= a[n-1]/a[i] + 1; j++) { int pos = lower_bound(a+i,a+n,j * a[i]) - a; pos -- ; if(pos > 0 && pos <= n && a[pos] > a[i]) ans = max(ans, a[pos] % a[i]); if(ans == a[i]-1) break;// cout << j <<" " << pos <<" " <
                 
                  << endl; } } print(ans); return 0;}