Advertisement
Guest User

Untitled

a guest
May 8th, 2016
235
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.62 KB | None | 0 0
  1.  
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. typedef long long ll;
  5. typedef unsigned long long ull;
  6. typedef vector<int> vi;
  7. typedef vector<ll> vll;
  8. int inf_int=2e9;
  9. ll inf_ll=2e18;
  10. typedef pair<int,int> pii;
  11. #define pb push_back
  12. const double pi=3.1415926535898;
  13. #define dout if(debug) cout
  14. #define fi first
  15. #define se second
  16. #define sp setprecision
  17. #define sz size()
  18.  
  19.  
  20. #define x1 gfgs
  21. #define y1 asd
  22. #define rank asdsad
  23. bool debug=0;
  24. const int maxn=5e5+107;
  25. ll mod=1e9+7;
  26.  
  27.  
  28.  
  29. void solve()
  30. {
  31. int n;
  32. cin >> n;
  33. int a[n];
  34. for(int i=0;i<n;i++)
  35. {
  36. cin >> a[i];
  37. }
  38. if(n==2)
  39. {
  40. cout << min(a[0],a[1])<<"\n";
  41. return;
  42. }
  43. int ans=1;
  44. int x=a[0];
  45. for(int i=1;i*i<=x;i++)
  46. {
  47.  
  48. if(x%i==0)
  49. {
  50. int nod2=-1;
  51. for(int e=1;e<n;e++)
  52. {
  53. if(a[e]%i==0)
  54. {
  55. continue;
  56. }
  57. else
  58. {
  59. if(nod2==-1)
  60. {
  61. nod2=a[e];
  62. }
  63. else
  64. {
  65. nod2=__gcd(nod2,a[e]);
  66. }
  67. if(nod2<ans)
  68. break;
  69. }
  70. }
  71. if(nod2==-1)
  72. {
  73. nod2=i;
  74. }
  75. ans=max(ans,min(nod2,i));
  76.  
  77. int del=x/i;
  78. nod2=-1;
  79. for(int e=1;e<n;e++)
  80. {
  81. if(a[e]%del==0)
  82. {
  83. continue;
  84. }
  85. else
  86. {
  87. if(nod2==-1)
  88. {
  89. nod2=a[e];
  90. }
  91. else
  92. {
  93. nod2=__gcd(nod2,a[e]);
  94. }
  95. if(nod2<ans)
  96. break;
  97. }
  98. }
  99. if(nod2==-1)
  100. {
  101. nod2=del;
  102. }
  103. ans=max(ans,min(nod2,del));
  104. }
  105. }
  106. cout << ans<<"\n";
  107.  
  108. }
  109.  
  110.  
  111. #define FILE "bridges"
  112. int main()
  113. {
  114.  
  115. // freopen("a.txt","r",stdin);
  116. // freopen("output.txt","w",stdout);
  117.  
  118. // freopen(FILE".in","r",stdin);
  119. // freopen(FILE".out","w",stdout);
  120. if(!debug)
  121. {
  122. ios_base::sync_with_stdio(0);
  123. cin.tie(0);
  124. cout.tie(0);
  125. }
  126. int t=1;
  127. cin >> t;
  128. while(t--)
  129. solve();
  130. return 0;
  131. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement