fork download
copy 
  1. #pragma GCC optimize ("unroll-loops")
  2. #pragma GCC optimize ("O3", "omit-frame-pointer","inline")
  3. #pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,fma,popcnt,abm,mmx,avx,avx2")
  4.  
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7.  
  8. /***********************************************/
  9. /* Dear online judge:
  10.  * I've read the problem, and tried to solve it.
  11.  * Even if you don't accept my solution, you should respect my effort.
  12.  * I hope my code compiles and gets accepted.
  13.  *  ___  __     _______    _______
  14.  * |\  \|\  \  |\  ___ \  |\  ___ \
  15.  * \ \  \/  /|_\ \   __/| \ \   __/|
  16.  *  \ \   ___  \\ \  \_|/__\ \  \_|/__
  17.  *   \ \  \\ \  \\ \  \_|\ \\ \  \_|\ \
  18.  *    \ \__\\ \__\\ \_______\\ \_______\
  19.  *     \|__| \|__| \|_______| \|_______|
  20.  */
  21. //const long long mod = 1000000007;
  22. const long long mod = 998244353;
  23. mt19937 rng((int) chrono::steady_clock::now().time_since_epoch().count());
  24.  
  25. const int mxN = 100010;
  26.  
  27. int main(int argc, char *argv[]) {
  28.     freopen("lcm.in","r",stdin);
  29. #ifdef ONLINE_JUDGE
  30. 	ios_base::sync_with_stdio(false);
  31. 	cin.tie(nullptr);
  32. //freopen("input.txt", "r", stdin);
  33. //freopen("output.txt", "w", stdout);
  34. #endif
  35.  
  36. 	srand(time(NULL));
  37. 	cout << fixed << setprecision(9);
  38.  
  39. 	int t = 1;
  40. //	int Case = 1;
  41. 	cin >> t;
  42. //	t = 10000;
  43. 	while (t--) {
  44. 		int n;
  45. 		long long l, r;
  46. 		cin >> n >> l >> r;
  47. 		vector<long long> a(n);
  48. 		for (int i = 0; i < n; i++)
  49. 			cin >> a[i];
  50. 		map<long long, int> lcm;
  51. 		int cnt_2 = 0;
  52. 		for (int i = 0; i < n; i++) {
  53. 		    cnt_2 = 0;
  54. 		    while(a[i]%2 == 0) {
  55. 		        a[i] /= 2;
  56. 		        cnt_2++;
  57. 		    }
  58. 		    if(cnt_2) lcm[2] = max(lcm[2], cnt_2);
  59. 			for (long long j = 3; j * j <= a[i]; j += 2)
  60. 				if (a[i] % j == 0) {
  61. 					int cnt = 0;
  62. 					while (a[i] % j == 0)
  63. 						a[i] /= j, cnt++;
  64. 					lcm[j] = max(lcm[j], cnt);
  65. 				}
  66. 			if (a[i] > 1) {
  67. 				lcm[a[i]] = max(lcm[a[i]], 1);
  68. 				a[i] = 1;
  69. 			}
  70. 		}
  71. 		long long res = r, mul = 1;
  72. 		for (long long x = r; x >= l; x--) {
  73. 			long long cur = x;
  74. 			for (auto &p : lcm)
  75. 				if (cur % p.first == 0) {
  76. 					for (int k = 0; k < p.second && cur % p.first == 0; k++)
  77. 						cur /= p.first;
  78. 				}
  79. 			if (cur > mul) mul = cur, res = x;
  80. 			if (cur == x) break;
  81. 		}
  82. 		cout << res << '\n';
  83. 	}
  84. 	return 0;
  85. }
  86.  
  87. /* stuff you should look for:
  88.  * overflow, array bounds
  89.  * special cases (n=1?)
  90.  * clear arrays
  91.  * DON'T STICK TO ONE APPROACH
  92.  * solve simpler or different variation
  93.  * Solve DP using graph ( \_(-_-)_/ )
  94.  */
  95.  
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
22956413292097
https://ideone.com/uBCJ9E
language:
C++ (gcc 8.3)
created:
4 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!