彼得和他的王国 2

注意：这和彼得和他的王国 1 有两点不同：1. 这里的彼得已经不可十世了，2. 因为不可十世，所以他的城市人口的数据范围较大

不可十世的彼得建立了彼氏王国，他的王国里有 $n$ 个城市。因为不可十世，所以彼得感到无聊，他开始转头研究起了人口统计和玄学。

根据人口统计学，彼得统计出了他的王国里每个城市中的人口数，如果我们把 $n$ 个城市从 $1$ 到 $n$ 依次编号，那么第 $i$ 个城市里有 $P_i$ 个人。

根据玄学，彼得认为数论中的[公因数]具有着神秘的力量。他开始细心研究任意两个城市的人口的对应着的公因数。

比如若彼得的城市对应的人口构成了一个序列： $[49, 24, 42]$ ，那么我们有：

第 $1$ 个城市和第 $2$ 个城市对应的公因数为： $1$ 。
第 $1$ 个城市和第 $3$ 个城市对应的公因数为： $1, 7$ 。
第 $2$ 个城市和第 $3$ 个城市对应的公约数为： $1, 2, 3, 6$ 。

那么彼得得到了 $1, 2, 3, 6, 7$ 这些数，他打算在这里面找出最大的公因数，是 $7$ 。但是问题总是残酷的：

然而现实总是残酷的，彼得的脑容量太小，无法处理太大的数，他决定只找到在 $[1, l]$ 的范围内最大的公因数。

比如彼得的大脑无法处理大于 $5$ 的数（没错，国王是不需要学数学的），那么他认为 $3$ 才是最大的公因数。

这个简单的任务对于彼得而言还是太难了，你能帮帮他吗？

第一行是两个整数，分别代表着 $l$ 和 $n$ ，其中 $1 \le l \le 2 \times 10^{11}$ 是彼得国王能处理的最大的数字，而 $2 \le n \le 1 \times 10^2$ 是彼得王国的城市的数目。

第二行有 $n$ 个整数，编号第 $1$ 个一直到第 $n$ 个，第 $i$ 个数字代表了 $2 \le P_i \le 2 \times 10^{11}$ ，即第 $i$ 个城市的人口数量。

#include<bits/stdc++.h> using namespace std; long long bns[110],result=0; int main() { long long sum1,sum2; cin>>sum1>>sum2; for(long long n=1;n<=sum2;n++) cin>>bns[n]; for(long long n=1;n<sum2;n++) for(long long m=n+1;m<=sum2;m++) { long long val=__gcd(bns[n],bns[m]); if(val>sum1) { for(long long i=sum1;i>=1;i--) { if(bns[n]%i==0&&bns[m]%i==0) { result=max(i,result); break; } } } else result=max(result,val); } cout<<result<<endl; return 0; }

l,n=list(map(int,input().split(" "))) lst=list(map(int,input().split(" "))) lst1=[] for i in lst: j=1 while j*j<=i: if i%j==0 and j<=l: lst1.append(j) if i//j<=l and j*j!=i: lst1.append(i//j) j+=1 lst2=list(set(lst1)) lst2.sort(reverse=True) for i in lst2: if lst1.count(i)>=2: print(i) break

详情