fork download
  1. /*
  2.  
  3. https://w...content-available-to-author-only...k.com/contests/uits251201g/challenges/the-grand-equalizer/problem
  4.  
  5. */
  6.  
  7. #include <bits/stdc++.h>
  8. using namespace std;
  9. #include <ext/pb_ds/assoc_container.hpp>
  10. #include <ext/pb_ds/tree_policy.hpp>
  11. using namespace __gnu_pbds;
  12. #define int long long
  13. #define ll long long
  14. #define lld long double
  15. #define pb push_back
  16. #define endl "\n"
  17. #define all(v) v.begin(), v.end()
  18. #define rall(v) v.rbegin(), v.rend()
  19. #define istg() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  20. template<class T> using ordered_set = tree<T, null_type,less<T>, rb_tree_tag,tree_order_statistics_node_update>;
  21. const ll M = 1e9 + 7;
  22. const ll N = 1e6 + 1;
  23. inline void normal(ll &a);
  24. inline ll modMul(ll a, ll b);
  25. inline ll modAdd(ll a, ll b);
  26. inline ll modSub(ll a, ll b);
  27. inline ll modPow(ll b, ll p);
  28. inline ll modInverse(ll a);
  29. inline ll modDiv(ll a, ll b);
  30. vector<bool>mark(N + 1);
  31. vector<ll>prime;
  32. void seive();
  33.  
  34. vector<ll>spf(N);
  35. void precal() {
  36. for (int i = 2; i < N; i++) {
  37. for (int j = i; j < N; j += i) {
  38. if (spf[j] == 0) {
  39. spf[j] = i;
  40. }
  41. }
  42. }
  43. // for (int i = 1; i < 11; i++) {
  44. // cout << spf[i] << endl;
  45. // }
  46. }
  47.  
  48. void solve(ll tc)
  49. {
  50. precal();
  51. int n; cin >> n;
  52. vector<ll> v(n);
  53. for (auto& i : v) cin >> i;
  54.  
  55. vector<ll> lf(N, 1);
  56. for (auto x : v) {
  57. while (x > 1) {
  58. int p = spf[x], val = 1;
  59. while (x % p == 0) {
  60. val *= p;
  61. x /= p;
  62. }
  63. lf[p] = max(lf[p], 1LL * val);
  64. }
  65. }
  66. // for (int i = 1; i < 11; i++) {
  67. // cout << lf[i] << endl;
  68. // }
  69. ll lcm = 1;
  70. for (int i = 2; i < N; i++) {
  71. lcm = modMul(lcm, lf[i]);
  72. }
  73. // cout << lcm << endl;
  74.  
  75. int ans = 0;
  76. for (auto i : v) {
  77. ans += modDiv(lcm, i);
  78. normal(ans);
  79. }
  80. cout << ans << endl;
  81.  
  82.  
  83. }
  84.  
  85. int32_t main()
  86. {
  87. istg();
  88. // freopen("input.txt", "r", stdin);
  89. // freopen("output.txt", "w", stdout);
  90. // seive();
  91. ll t = 1;
  92. // cin >> t;
  93. for (ll i = 1; i <= t; i++) solve(i);
  94.  
  95. }
  96.  
  97. void seive(){
  98. mark[0]=true;
  99. mark[1]=true;
  100. for(ll i=4; i<=N; i+=2){
  101. mark[i]=true;
  102. }
  103. for(ll i=3; i*i<=N; i+=2){
  104. if(mark[i]==false){
  105. for(ll j=i*i; j<=N; j+=2*i){
  106. mark[j]=true;
  107. }
  108. }
  109. }
  110. prime.push_back(2);
  111. for(ll i=3; i<=N; i+=2){
  112. if(mark[i]==false){
  113. prime.push_back(i);
  114. }
  115. }
  116.  
  117. }
  118.  
  119. inline void normal(ll &a) {
  120. a = (a % M + M) % M;
  121. }
  122. inline ll modMul(ll a, ll b) {
  123. normal(a);
  124. normal(b);
  125. return (a * b) % M;
  126. }
  127. inline ll modAdd(ll a, ll b) {
  128. normal(a);
  129. normal(b);
  130. return (a + b) % M;
  131. }
  132. inline ll modSub(ll a, ll b) {
  133. normal(a);
  134. normal(b);
  135. a -= b;
  136. normal(a);
  137. return a;
  138. }
  139. inline ll modPow(ll b, ll p) {
  140. ll r = 1;
  141. while (p) {
  142. if (p & 1) r = modMul(r, b);
  143. b = modMul(b, b);
  144. p >>= 1;
  145. }
  146. return r;
  147. }
  148. inline ll modInverse(ll a) {
  149. return modPow(a, M - 2);
  150. }
  151. inline ll modDiv(ll a, ll b) {
  152. return modMul(a, modInverse(b));
  153. }
  154.  
Success #stdin #stdout 0.06s 18768KB
stdin
Standard input is empty
stdout
0