EXPGCD Approach?

Please share your approach for EXPGCD for September long challenge 2019.
I tried to use combinatorics. But was not able to pass subtask 3 :slight_smile:

1 Like

You will understand this if our combinatorics soln ( O(N/K) or O(N) for each test case) was same.

You just need to observe and optimize your approach ( O(N) per test case or O(N/K) per test case) for 100.
Print result for n=1 and n=2 and so on and see difference b/w array of N=k and N=k+1.
( array[i] = number of subsets of size K with gcd = i )
You will see that only few values will change in array (index = divisors of k+1).
Just use result of N=k for computing N=k+1 and you will get 100.

Though i couldn’t solve this question, it was fun for me. For k = 2 the similar qustion is there
on Spoj named GCDEX. It can be solved using Euler’s Totient Function. There’s another question
on Spoj GCDEX2 which is harder version of it. And the same method would tle. But this man over
here answer how to do it which has enough of summations signs to scare me :smiley: so i followed half
of it and extended my solution for higher values of K. But turns out it ain’t enough and my solution runs out for smaller values of K. Would love to know standard method.

Ah ! thanks for your approach . Problem was I thought about combinatorics after I had passed subtask 2 ( which used other approach :stuck_out_tongue: )

1 Like

Check my answer above. I guess were on same page :stuck_out_tongue:


My intended solution was to use inclusion exclusion.
First i calculated factors of all numbers in nlogn.
Then i initialized dp[i] as iC(k-1).
After that i used all the factors of current i to subtract all pairs whose gcd is not 1 from dp[i].
After this, you can calculate sum of gcd using something similar like euler’s totient and precalculate answers for all n.
The editorial will be released soon, which will contain the code of my solution.
Hope you liked my question. :slight_smile:


Pretty standard trick…

\displaystyle \sum_{1 \leq i_1 < ... < i_k \leq n} \gcd(i_1, ..., i_k) = \sum_{1 \leq i_1 \leq ... \leq i_k \leq n} \sum_{d | gcd(i_1, ..., i_k)} \phi(d) = \sum_{1 \leq i_1 < ... < i_k \leq n} \sum_{d | i_1, ..., i_k} \phi(d) = \sum_{d\leq n} \binom{\lfloor\frac{n}{d}\rfloor}{k} \phi(d)

Now, \displaystyle \sum_{d\leq n} \binom{\lfloor\frac{n}{d}\rfloor}{k} \phi(d) = \sum_{d\leq n - 1}\binom{\lfloor\frac{n - 1}{d}\rfloor}{k} \phi(d) + \sum_{d | n} \binom{\frac{n}{d} - 1}{k - 1} \phi(d)

because \lfloor\frac{n}{d}\rfloor = \lfloor\frac{n - 1}{d}\rfloor unless d | n, in which case \lfloor\frac{n}{d}\rfloor = \lfloor\frac{n - 1}{d}\rfloor + 1. (Also note that we used \binom{u}{k - 1} + \binom{u}{k} = \binom{u + 1}{k}.) This then allows us to pre-compute the answers for all allowable n in sufficient time. My code: