### Dijkstra.'s blog

By Dijkstra., history, 2 years ago,

The 2018 Egyptian Collegiate Programming Contest was held yesterday this was a problem from it where he asks for

Where n<=10^5 and a[i]<=10^5 answer should be printed %10^9+7

I would appreciate any help in solving this problem and thanks in advance

• +30

 » 2 years ago, # |   0 Auto comment: topic has been updated by Dijkstra. (previous revision, new revision, compare).
 » 2 years ago, # | ← Rev. 2 →   +33 hintinclusion exclusion solution ideaFor a fixed g how many pairs that will have this g as a gcd, it'll be all multiples of g, it's easy to get the sum of multiplying those pairs.but there is a problem with this, there will be some pairs that will be calculated multiple times, so we have to exclude the answer of (2 * g, 3 * g, ...), for example if we are solving when g = 2 we know that all the numbers divisible by 4 is also divisible by 2, so we have to exclude the answer of 4, and so on.so the answer is iterate from the max number in descending order to 1 and solve for each fixed g, the total complexity of this solution is code#include using namespace std; const int N = 100005; const int mod = (int) 1e9 + 7; int n, mx; int a[N]; int cnt[N]; int ans[N]; long long inv[N]; void init() { inv[0] = inv[1] = 1; for (int i = 2; i < N; i++) { inv[i] = (mod - (mod / i) * inv[mod % i] % mod) % mod; } } int solve(int g) { long long sum = 0, res = 0; for (int i = g; i <= mx; i += g) { (sum += cnt[i] * 1LL * i % mod) %= mod; } for (int i = g; i <= mx; i += g) { (res += cnt[i] * 1LL * i % mod * sum % mod) %= mod; } (res *= inv[g]) %= mod; for (int i = 2 * g; i <= mx; i += g) { res -= ans[i] * 1LL * i % mod * inv[g] % mod; if (res < 0) res += mod; } return ans[g] = res; } int main() { init(); int t; scanf("%d", &t); while (t--) { scanf("%d", &n); memset(cnt, 0, sizeof cnt); memset(ans, 0, sizeof ans); mx = 0; for (int i = 0; i < n; i++) { scanf("%d", a + i); cnt[a[i]]++; mx = max(mx, a[i]); } int res = 0; for (int g = mx; g > 0; g--) { (res += solve(g)) %= mod; } printf("%d\n", res); } return 0; } 
•  » » 13 months ago, # ^ |   0 Why do you need to, if for example g=2, to exclude twice the answer of 4?
•  » » » 13 months ago, # ^ |   0 EDIT: I got it. It turns out that in the calculation of g=2, I overcount the pairs that have 4 as a gcd and I count them as having 2 as a gcd... In the ans[4], they are divided by 4 (their gcd), so to remove the overcounting I multiply the ans[4] by 2.
 » 2 years ago, # |   +25 Mhm... nice problem. Do you agree, mnbvmar?
•  » » 2 years ago, # ^ | ← Rev. 3 →   +27 <3Story: We proposed this exact task (under a tiny bit different constraints, though) to our high school students back in 2015. I was quite surprised that apparently it has never appeared anywhere even though the statement feels really natural and obvious. So it seems it eventually did!I think Proszek_na_ludka came up with another solution, involving... Spoilerthe Möbius inversion formulaI can't remember any details, though. Mind sharing (if you still remember it)?
•  » » » 2 years ago, # ^ | ← Rev. 2 →   +14 SolutionFirst I calculated an array B[n] such, that (how: first set , then for each i from 1 to n iterate over all multiples of i and subtract B[i] from B[di]).Now we can just iterate over all possible d and add to accumulator sum of entries divisible by d squared times B[d]. This way for each pair a[i], a[j] we have added , which is equal to The only moment where Möbius inversion formula came into play was calculating B[n] array. It can also be done using that formula, but the way I posted here is much easier. I think i used this approach on that contest back in 2015, but I'm not sure