### AshutoshChoudhary's blog

By AshutoshChoudhary, history, 2 months ago,

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

 » 2 months ago, # |   -7 u can use gcd convulation
•  » » 2 months ago, # ^ |   0 I'm unaware about that technique, can you please describe the algorithm ?
•  » » 2 months ago, # ^ |   +1 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
•  » » » 2 months ago, # ^ |   0 please show the implementation
•  » » » » 2 months ago, # ^ | ← Rev. 2 →   0 Spoiler/** * author: phares * created: at some point **/ #include 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> 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 cnt(int(1e5 + 1)); for (int i = 0; i < n; i++) { int x; cin >> x; ++cnt[x]; } vector 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; }
•  » » » » » 2 months ago, # ^ |   0 isn't it n square solution?
•  » » » » » » 2 months ago, # ^ |   0 no
•  » » » » » » 2 months ago, # ^ |   +3 It's nlogn like sieve of erato something
•  » » » » » 7 weeks ago, # ^ | ← Rev. 3 →   0 .
•  » » » » » » 7 weeks ago, # ^ |   0 it's an upper bound for harmonic series
 » 2 months ago, # |   +14 you can dp on number of pairs with gcd x, an then simply sum and multiply
 » 2 months ago, # | ← Rev. 2 →   +3
 » 2 months ago, # |   +1 you may look at submissions / Tutorial for this problemit discus the same idea you talk about....
•  » » 2 months ago, # ^ | ← Rev. 2 →   +1 This one is also kinda similar