Advertisement
tumaryui

Untitled

May 12th, 2020
112
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.36 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. //#pragma GCC optimize("Ofast")
  3. //#pragma GCC target("avx,avx2,fma")
  4. //#pragma GCC optimization ("unroll-loops")
  5.  
  6. #define int long long
  7. #define pb push_back
  8. #define all(s) s.begin(),s.end()
  9. #define pii pair<int,int>
  10. #define fr first
  11. #define sc second
  12. #define bst ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  13. #define endl "\n"
  14.  
  15. using namespace std;
  16.  
  17. const int N = 1e5 + 10, mod = 1e9 + 7, inf = 1e18 + 7;
  18. const double pi = acos(-1);
  19.  
  20. int lp[2 * N+1];
  21. vector<int> pr;
  22.  
  23. void solve() {
  24. //soln
  25. int n;
  26. cin >> n;
  27. int a[n];
  28. for(int i = 0; i < n; i++) {
  29. cin >> a[i];
  30. }
  31. if(n == 1) {
  32. cout << a[0] << endl;
  33. return;
  34. }
  35. int ans = 1;
  36. for(int i = 0; pr[i] * pr[i] <= N; i++) {
  37. map<int, int> mp;
  38. for(int j = 0; j < n; j++ ){
  39. int pw = 0, tmp = a[j];
  40. while(tmp % pr[i] == 0) {
  41. tmp /= pr[i];
  42. pw++;
  43. }
  44. if(mp.count(pw) == 0) {
  45. mp.insert({pw, 1});
  46. } else {
  47. mp[pw]++;
  48. }
  49. }
  50.  
  51. for(auto it: mp) {
  52. if(it.second >= 2) {
  53. ans *= pow(pr[i], it.first);
  54. break;
  55. }
  56.  
  57. }
  58. }
  59. cout << ans << endl;
  60. }
  61. main() {
  62. bst;
  63. for (int i=2; i<=N; ++i) {
  64. if (lp[i] == 0) {
  65. lp[i] = i;
  66. pr.push_back (i);
  67. }
  68. for (int j=0; j<(int)pr.size() && pr[j]<=lp[i] && i*pr[j]<=N; ++j)
  69. lp[i * pr[j]] = pr[j];
  70. }
  71. int t = 1;
  72. //cin >> t;
  73. while(t--) {
  74. solve();
  75. }
  76. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement