再学一道算法题：监控

某国的安全部门监控了全国的数据流，该部门的程序员接到一个任务，恐怖组织会给手下发送一个数字序列A，其中由n个正整数组成，而其中任何两个值Ai和Aj都可以求它们的余数

x=Ai mod Aj ，（其中1<=i,j<=n，Ai>= Aj）。

所有x中，最大的x就是破译机密的秘钥。程序员的任务就是找到这个最大的x。

输入格式:
第一行是一个正整数n，第二行由n个小于等于10
6
的正整数组成
1 ≤ n ≤ 2·10
5

输出格式:
输出找到的最大值。

输入样例:
3
1 3 10
输出样例:
1
水题，注意，a%b的余数绝对不会比b大，所以从大到小排序后，只要最大余数不小于后面的数后就可结束

#include<algorithm>
#include<iostream>
#include<map>
using namespace std;
int a[2000005];
bool cmp(int a,int b)
{
                return a>b;
}
int main()
{
                int n;
                scanf("%d",&n);
                for(int i=0;i<n;i++)
                {
                                scanf("%d",&a[i]);
                }
                sort(a,a+n,cmp);
                int max=0;
                for(int i=0;i<n;i++)
                {
                                if(max>=a[i])break;
                                for(int j=i+1;j<n;j++)
                                {
                                                if(a[j]&&a[i]%a[j]>max)
                                                max=a[i]%a[j];
                                }
                }
                printf("%d\n",max);
                return 0;
}



        

          
        
        
        

          

          AI 代码解读