fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. typedef long double ld;
  7. typedef pair<int, int> pii;
  8. typedef pair<ll, ll> pll;
  9. typedef vector<int> vi;
  10.  
  11. #define fi first
  12. #define se second
  13. #define pp push_back
  14. #define all(x) (x).begin(), (x).end()
  15. #define Ones(n) __builtin_popcount(n)
  16. #define endl '\n'
  17. #define mem(arrr, xx) memset(arrr,xx,sizeof arrr)
  18. //#define int long long
  19. #define debug(x) cout << (#x) << " = " << x << endl
  20.  
  21. void Gamal() {
  22.     ios_base::sync_with_stdio(false);
  23.     cin.tie(nullptr);
  24.     cout.tie(nullptr);
  25. #ifdef Clion
  26.     freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
  27. #endif
  28. }
  29.  
  30. int dx[] = {+0, +0, -1, +1, +1, +1, -1, -1};
  31. int dy[] = {-1, +1, +0, +0, +1, -1, +1, -1};
  32.  
  33. const double EPS = 1e-9;
  34. const ll OO = 0X3F3F3F3F3F3F3F3F;
  35. const int N = 1e5 + 5, INF = INT_MAX, MOD = 1e9 + 7, LOG = 20;
  36.  
  37. vector<int> divs[N];
  38.  
  39. void build() {
  40.     for (int i = 1; i < N; ++i) {
  41.         for (int j = i; j < N; j += i) {
  42.             divs[j].push_back(i);
  43.         }
  44.     }
  45. }
  46.  
  47. ll mul(const ll &a, const ll &b) {
  48.     return (a % MOD + MOD) * (b % MOD + MOD) % MOD;
  49. }
  50.  
  51. ll add(const ll &a, const ll &b) {
  52.     return (a + b + 2 * MOD) % MOD;
  53. }
  54.  
  55. ll pw(ll b, ll p) {
  56.     if (p < 0)return 0;
  57.     if (!p) return 1LL;
  58.     ll ret = pw(b, p >> 1LL);
  59.     ret = mul(ret, ret);
  60.     if (p & 1LL)
  61.         ret = mul(ret, b);
  62.     return ret;
  63. }
  64.  
  65.  
  66. ll dp[N], sum[N];
  67.  
  68. void solve() {
  69.     int n;
  70.     cin >> n;
  71.     mem(dp, 0);
  72.     mem(sum, 0);
  73.     ll ans = 0,tot = 0;
  74.     for (int i = 0; i < n; ++i) {
  75.         int x;
  76.         cin >> x;
  77.         tot += x;
  78.         for (auto d: divs[x]) {
  79.             dp[d] = add(dp[d], mul(x, sum[d]));
  80.             sum[d] = add(sum[d], x);
  81.         }
  82.     }
  83.  
  84.     for (int i = N - 1; i >= 1; --i) {
  85.         for (int j = 2 * i; j < N; j += i) {
  86.             dp[i] = add(dp[i], -dp[j]);
  87.         }
  88.         ans = add(ans, mul(dp[i], pw(i, MOD - 2)));
  89.     }
  90.     ans = add(mul(2,ans),tot);
  91.     cout << ans << endl;
  92. }
  93.  
  94.  
  95. signed main() {
  96.     Gamal();
  97.     freopen("lcm.in","r",stdin);
  98.     build();
  99.     int t = 1;
  100.     cin >> t;
  101.     while (t--) {
  102.         solve();
  103.     }
  104. }
Success #stdin #stdout 0.12s 15652KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/3pCohb
language:
C++ (gcc 8.3)
created:
3 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!