fork download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/rRW0ri
language:
C++14 (gcc 8.3)
created:
8 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!