fork download
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. using bs = unsigned long long;
  4. using pi = pair<int, int>;
  5. const int MAXN = 100005;
  6.  
  7. int chk[MAXN];
  8. bs msk[2000];
  9.  
  10. void upload(int s, int l){
  11. auto get_slowa = [&](int s, int l){
  12. bs ret = 0;
  13. ret |= (msk[s >> 6] >> (s & 63));
  14. if(s & 63){
  15. auto fu = msk[(s >> 6) + 1] & ((1ull << (s & 63)) - 1ull);
  16. ret |= (fu << (64 - (s & 63)));
  17. }
  18. if(l < 64) ret &= (1ull << l) - 1ull;
  19. return ret;
  20. };
  21. for(int i=0; i<l; i+=64){
  22. auto slowa = get_slowa(s + i, min(64, l - i));
  23. msk[i >> 6] |= slowa;
  24. }
  25. }
  26.  
  27. int main(){
  28. int n; scanf("%d",&n);
  29. int minv = 1e9;
  30. for(int i=0; i<n; i++){
  31. int x; scanf("%d",&x);
  32. minv = min(minv, x);
  33. chk[x]++;
  34. }
  35. if(chk[minv] == 1){
  36. cout << minv << endl;
  37. return 0;
  38. }
  39. for(int i=100000; i>minv; i--){
  40. if(chk[i] == 0) continue;
  41. for(int j=i; j<=100000; j+=i){
  42. upload(j, min(i, 100001 - j));
  43. }
  44. msk[i >> 6] |= (1ull << (i & 63));
  45. }
  46. int ret = 0;
  47. for(int i=100000; i>=0; i--){
  48. if((msk[i >> 6] >> (i & 63)) & 1){
  49. ret = max(ret, i % minv);
  50. }
  51. }
  52. cout << ret << endl;
  53. }
  54.  
  55.  
Time limit exceeded #stdin #stdout 5s 15640KB
stdin
Standard input is empty
stdout
Standard output is empty