[Question] — Sum of value of GCD for all possible pairs

Блог пользователя AshutoshChoudhary

Автор AshutoshChoudhary, история, 3 месяца назад, По-английски

Q: Given an array of n integers, find the sum of value of GCD for all possible pairs.

2 <= n <= 10 ^ 5

1 <= a[i] <= 10 ^ 5

gcd

AshutoshChoudhary
3 месяца назад
14

Комментарии (14)

Написать комментарий?

aryxn5

3 месяца назад, # |

-7

u can use gcd convulation

→ Ответить

AshutoshChoudhary

3 месяца назад, # ^ |

I'm unaware about that technique, can you please describe the algorithm ?

→ Ответить

aryxn5

3 месяца назад, # ^ |

or what we can do is count no.of pairs having (gcd=x) for every x from 1 to 1e5 using dp,now iterate over this x,so your answer is summation(x*(cnt)),this is standard question,ping me if you want implementation

→ Ответить

pokeland157

3 месяца назад, # ^ |

please show the implementation

→ Ответить

reowong

3 месяца назад, # ^ |

← Rev. 2 →

Spoiler

/**
 *    author:  phares  
 *    created: at some point
**/
#include <bits/stdc++.h>

using namespace std;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int tt = 1;;
  //cin >> tt;;
  while (tt--) {
    vector<vector<int>> d(int(1e5 + 1));
    for (int i = 1; i <= int(1e5); i++) {
      for (int j = i; j <= int(1e5); j += i) {
        d[j].push_back(i);
      }
    }
    int n;
    cin >> n;
    vector<int> cnt(int(1e5 + 1));
    for (int i = 0; i < n; i++) {
      int x;
      cin >> x;
      ++cnt[x];
    }
    vector<long long> dp(int(1e5 + 1));
    for (int i = int(1e5); i >= 1; i--) {
      long long s = 0;
      for (int j = i; j <= int(1e5); j += i) {
        s += cnt[j];
      }
      s = s * s - s >> 1ll;
      for (int j = i + i; j <= int(1e5); j += i) {
        s -= dp[j];
      }
      dp[i] = s;
    }
    long long ans = 0;
    for (int i = 1; i <= int(1e5); i++) {
      ans += dp[i] * i;
    }
    cout << ans << '\n';
  }
  return 0;
}

→ Ответить