首页 > 代码库 > 1421 最大MOD值

1421 最大MOD值

2024-08-12 11:42:16   210人阅读

1421 最大MOD值
基准时间限制：1 秒 空间限制：131072 KB 

有一个a数组，里面有n个整数。现在要从中找到两个数字(可以是同一个) ai,aj ，使得 ai mod aj 最大并且 ai ≥ aj。

Input
单组测试数据。第一行包含一个整数n，表示数组a的大小。(1 ≤ n ≤ 2*10^5)第二行有n个用空格分开的整数ai (1 ≤ ai ≤ 10^6)。
Output
输出一个整数代表最大的mod值。
Input示例
33 4 5
Output示例
2
思路：二分；
找最大的mod，我们先去重，然后循环每个数的倍数，二分找小余倍数的最大的值，这个用筛法，然后更新最大的答案。复杂度n*(logn)^2;
 1 #include<stdio.h> 2 #include<algorithm> 3 #include<string.h> 4 #include<math.h> 5 #include<stdlib.h> 6 #include<queue> 7 #include<iostream> 8 int ans[300000]; 9 int bns[300000];10 int ap[1000005];11 using namespace std;12 int main(void) {13     int n;14     scanf("%d",&n);15     int i,j;16     int maxx = 0;17     for(i = 0; i < n; i++) {18         scanf("%d",&ans[i]);19         maxx = max(ans[i],maxx);20     }21     sort(ans,ans+n);22     int cn = 0;23     bns[cn++] = ans[0];24     int t =bns[0];25     for(i = 1; i < n; i++) {26         if(ans[i]!=t) {27             t = ans[i];28             bns[cn++] = t;29         }30     }31     if(n == 1) {32         printf("0\n");33     } else {34         int ask = 0;35         for(i = cn-1; i >= 0; i--) {36             if(bns[i]!=1) {37                 for(j = 2; bns[i]*j <= maxx+bns[i]; j++) {38                     int l = i+1,r = cn-1;39                     int id = -1;40                     while(l <= r) {41                         int mid = (l+r)/2;42                         if(bns[mid] < bns[i]*j) {43                             id = mid;44                             l = mid + 1;45                         } else r = mid-1;46                     }47                     if(id!=-1) 48                         ask = max(bns[id]%bns[i],ask);49                 }50             }51             if(ask >= bns[i])break;52         }53         printf("%d\n",ask);54     }55     return 0;56 }

 

1421 最大MOD值






























        

            
                
                  
                
                

                    联系

                    我们