# RANDCHCL - Editorial

**URL:** <https://discuss.codechef.com/t/randchcl-editorial/57803>\
**Category:** editorial\
**Tags:** combinatorics, editorial, medium, cook116, tmwilliamlin\
**Created:** [March 22, 2020, 6:35pm UTC](https://discuss.codechef.com/t/randchcl-editorial/57803 "2020-03-22T18:35:27Z")\
**Posts on this page:** 12\
**Page:** 1

<div class="post-metadata">

**Author:** ![tmwilliamlin](https://discuss.codechef.com/user_avatar/discuss.codechef.com/tmwilliamlin/32/9076_2.png) [@tmwilliamlin](https://discuss.codechef.com/u/tmwilliamlin)\
**Post date:** [March 22, 2020, 6:35pm UTC](https://discuss.codechef.com/t/randchcl-editorial/57803/1 "2020-03-22T18:35:27Z")

</div>

# PROBLEM LINK:

[Practice](https://www.codechef.com/problems/RANDCHCL)  
[Div-1 Contest](https://www.codechef.com/COOK116A/problems/RANDCHCL)

_Author:_ [Anik Sarker](https://www.codechef.com/users/imAnik)  
_Tester:_ [Raja Vardhan Reddy](https://www.codechef.com/users/raja1999)  
_Editorialist:_ [William Lin](https://www.codechef.com/users/tmwilliamlin)

# DIFFICULTY:

Medium

# PREREQUISITES:

Combinatorics

# PROBLEM:

Given an array W of length N, find the expected score from the following process:

- Choose an integer k between 1 and N uniformly randomly.
- Let A be k not necessarily distinct elements chosen uniformly randomly and independently from W.
- Let B be chosen in the same way as A.
- The score is \sum\_{i=1}^k \sum\_{j =1}^k \gcd(A\_i, B\_j).

# QUICK EXPLANATION:

The score is just k^2 times the expected value of \gcd(W\_i, W\_j), so the answer is just the expected value of k^2 times the expected value of \gcd(W\_i, W\_j). To find the expected value of \gcd(W\_i, W\_j), we will iterate over all g and count the number of pairs such that \gcd(W\_i, W\_j)=g.

# EXPLANATION:

Note that the score is just k^2 times the expected value of \gcd(W\_i, W\_j), where i and j are chosen uniformly randomly.

> **Proof**
>
> All A\_i are chosen in the same way, and the same is true for all B\_j. Thus, there is no reason for the expected value of \gcd(A\_i, B\_j) to be different for the k^2 pairs (i, j).

Since k is independent from \gcd(W\_i, W\_j), the answer is the expected value of k^2 times the expected value of \gcd(W\_i, W\_j).

We can easily calculate the expected value of k^2.

> **Explanation**
>
> Add up k^2 for k from 1 to N and divide by N. Alternatively, use the well-known formula for the sum of the first k squares, which is \frac{k(k+1)(2k+1)}{6}.

What remains is to calculate the expected value of \gcd(W\_i, W\_j), which is the same as the sum of all \gcd(W\_i, W\_j) divided by N^2.

Finding the sum of all \gcd(W\_i, W\_j) is a well-known problem.

> **Explanation**
>
> First, we will calculate a frequency array c of all the elements in W. Then, we will calculate an array d such that d\_i is the number of elements in W which are multiples of i. The pseudocode is shown below:
> 
> ```auto
> for i from 1 to MAX:
> j = i
> while j <= MAX:
> d[i] += c[j]
> j += i
> 
> ```
> 
> The total time can be approximated by \sum\_{i = 1}^{N} \frac{N}{i}, which is well-known to be equal to O(N \log N) (approximate the sum with an integral).
> 
> Next, set d\_i to d\_i^2, so d\_i now represents the number of pairs of elements in W such that both elements of the pair are multiples of i.
> 
> Note that d\_i also represents the number of pairs such that the gcd of the first element and the second element is a multiple of i. Next, we want to find e\_i, which is the number of pairs such that the gcd of the first element and the second element is exactly i. We can find e\_i with complementary counting. We subtract all cases when the gcd isn’t exactly i but is a multiple of i:
> 
> ```auto
> for i from MAX to 1:
> e[i] = d[i]*d[i]
> j = 2*i
> while j <= MAX:
> e[i] -= e[j]
> j += i
> 
> ```
> 
> The final sum of the gcd over all pairs can be found by summing up i\cdot e\_i.

The total time complexity is O(N \log N), where N also represents the maximum value in W.

# SOLUTIONS:

> **Setter's Solution**
>
> ```auto
> #include <bits/stdc++.h>
> using namespace std;
>  
> const int maxn = 300005;
> const int maxv = 500005;
> const int mod = 998244353;
>  
> int add(int a, int b) {return (a + b) >= mod ? a + b - mod : a + b;}
> int sub(int a, int b) {return add(a, mod - b);}
> int mul(int a, int b) {return a * 1LL * b % mod;}
> int bigMod(int n, int r){
> int res = 1;
> int cur = n;
> while(r){
> if(r & 1) res = mul(res, cur);
> cur = mul(cur, cur);
> r >>= 1;
> }
> return res;
> }
> int Div(int a, int b) {return mul(a, bigMod(b, mod-2));}
>  
> namespace NumberTheory{
> int mob[maxv];
> int phi[maxv];
>  
> void sieve(){
> mob[1] = 1;
> for(int i=1; i<maxv; i++){
> for(int j=i; j<maxv; j+=i){
> if(j > i) mob[j] -= mob[i];
> }
> }
>  
> for(int i=1; i<maxv; i++){
> for(int j=i; j<maxv; j+=i){
> phi[j] += i * mob[j / i];
> }
> }
> }
> }
> using namespace NumberTheory;
>  
> int a[maxn];
> int occ[maxv];
> int cnt[maxv];
>  
> int main(){
> sieve();
>  
> int t;
> scanf("%d", &t);
>  
> for(int cs=1; cs<=t; cs++){
> int n, v;
> scanf("%d", &n);
>  
> for(int i=1; i<=n; i++) {scanf("%d", &v); occ[v]++;}
> for(int v=1; v<maxv; v++) for(int w=v; w<maxv; w+=v) cnt[v] += occ[w];
>  
> int P = 0;
> for(int i=1; i<maxv; i++){
> int curr = cnt[i];
> curr = mul(curr, curr);
> P = add(P, mul(curr, phi[i]));
> }
> P = Div(P, mul(n, n));
>  
> int Q = 0;
> for(int i=1; i<=n; i++) Q = add(Q, mul(i, i));
> Q = Div(Q, n);
>  
> printf("%d\n", mul(P, Q));
> for(int v=1; v<maxv; v++) occ[v] = 0, cnt[v] = 0;
> }
> }
> 
> ```

> **Tester's Solution**
>
> ```auto
> //raja1999
>  
> //#pragma comment(linker, "/stack:200000000")
> //#pragma GCC optimize("Ofast")
> //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
>  
> #include <bits/stdc++.h>
> #include <vector>
> #include <set>
> #include <map>
> #include <string> 
> #include <cstdio>
> #include <cstdlib>
> #include <climits>
> #include <utility>
> #include <algorithm>
> #include <cmath>
> #include <queue>
> #include <stack>
> #include <iomanip> 
> #include <ext/pb_ds/assoc_container.hpp>
> #include <ext/pb_ds/tree_policy.hpp> 
> //setbase - cout << setbase (16)a; cout << 100 << endl; Prints 64
> //setfill - cout << setfill ('x') << setw (5); cout << 77 <<endl;prints xxx77
> //setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
> //cout.precision(x) cout<<fixed<<val; // prints x digits after decimal in val
>  
> using namespace std;
> using namespace __gnu_pbds;
> #define f(i,a,b) for(i=a;i<b;i++)
> #define rep(i,n) f(i,0,n)
> #define fd(i,a,b) for(i=a;i>=b;i--)
> #define pb push_back
> #define mp make_pair
> #define vi vector< int >
> #define vl vector< ll >
> #define ss second
> #define ff first
> #define ll long long
> #define pii pair< int,int >
> #define pll pair< ll,ll >
> #define sz(a) a.size()
> #define inf (1000*1000*1000+5)
> #define all(a) a.begin(),a.end()
> #define tri pair<int,pii>
> #define vii vector<pii>
> #define vll vector<pll>
> #define viii vector<tri>
> #define mod (998244353LL)
> #define pqueue priority_queue< int >
> #define pdqueue priority_queue< int,vi ,greater< int > >
> #define int ll
>  
> typedef tree<
> int,
> null_type,
> less<int>,
> rb_tree_tag,
> tree_order_statistics_node_update>
> ordered_set;
>  
>  
> //std::ios::sync_with_stdio(false);
>  
> int power(int a,int b){
> int res=1;
> while(b>0){
> if(b%2){
> res*=a;
> res%=mod;
> }
> a*=a;
> a%=mod;
> b/=2;
> }
> return res;
> }
> int cnt[1123456],w[1123456],gg[1123456],haha[1123456];
> main(){
> std::ios::sync_with_stdio(false); cin.tie(NULL);
> int t,i,j;
> cin>>t;
> while(t--){
> int n;
> cin>>n;
> rep(i,n){
> cin>>w[i];
> }
> int s=0,ans=0;
> for(i=0;i<n;i++){
> haha[w[i]]++;
> s+=w[i];
> s%=mod;
> }
> for(i=1;i<=500005;i++){
> cnt[i]=0;
> for(j=i;j<=500005;j+=i){
> cnt[i]+=haha[j];
> }
> }
> fd(i,500005,1){
> gg[i]=cnt[i]*(cnt[i]-1);
> for(j=i*2;j<=500005;j+=i){
> gg[i]-=gg[j];
> }
> s+=(gg[i]*i)%mod;
> s%=mod;
> }
> f(i,1,n+1){
> ans+=(i*i)%mod;
> ans%=mod;
> }
> ans*=s;
> ans%=mod;
> ans*=power((n*n*n)%mod,mod-2);
> ans%=mod;
> cout<<ans<<endl;
> rep(i,n){
> haha[w[i]]--;
> }
> }
> return 0;
> }
> 
> ```

> **Editorialist's Solution**
>
> ```auto
> #include <bits/stdc++.h>
> using namespace std;
> 
> #define ll long long
> 
> const int mxN=3e5, mxW=5e5, M=998244353;
> int n;
> ll iv[mxN+1], c[mxW+1], d[mxW+1];
> 
> void solve() {
> //input
> cin >> n;
> memset(c, 0, 8*(mxW+1));
> for(int i=0, w; i<n; ++i)
> cin >> w, ++c[w];
> 
> //find # multiples for each i
> for(int i=1; i<=mxW; ++i)
> for(int j=i; (j+=i)<=mxW; )
> c[i]+=c[j];
> //find sum of gcd of pairs
> ll ans=0;
> for(int i=mxW; i; --i) {
> d[i]=c[i]*c[i];
> //subtract those with bigger gcd
> for(int j=i; (j+=i)<=mxW; )
> d[i]-=d[j];
> //add to ans
> ans=(ans+d[i]*i)%M;
> }
> 
> //multiply by n*(n+1)*(2*n+1)/6/n^3
> cout << ans*(n+1)%M*(2*n+1)%M*iv[6]%M*iv[n]%M*iv[n]%M << "\n";
> }
> 
> int main() {
> ios::sync_with_stdio(0);
> cin.tie(0);
> 
> //modular inverses
> iv[1]=1;
> for(int i=2; i<=mxN; ++i)
> iv[i]=M-M/i*iv[M%i]%M;
> 
> int t;
> cin >> t;
> while(t--)
> solve();
> }
> 
> ```

Please give me suggestions if anything is unclear so that I can improve. Thanks 🙂

---

<div class="post-metadata">

**Author:** ![induber](https://discuss.codechef.com/user_avatar/discuss.codechef.com/induber/32/26490_2.png) [@induber](https://discuss.codechef.com/u/induber)\
**Post date:** [March 22, 2020, 10:55pm UTC](https://discuss.codechef.com/t/randchcl-editorial/57803/4 "2020-03-22T22:55:24Z")

</div>

well, i have a different solution for this,lets calculate how many times an element will occur in all the possible distribution of the elements in A, let it be x. same will happen for B. So each element will occur in B x times, so each GCD pair will occur x\*x times.

So our final answer will be {(1/N) \* ( Summation (i = 1 to N) [((1/N)^(2 \* i)) \* `(x\*x) \* (all pair gcd sum)])}.  
where x = i \* (power(n, i) - (n-1)\*power(n, i-1)) .

[Solution Link](https://www.codechef.com/viewsolution/30675160)

---

<div class="post-metadata">

**Author:** ![tarun\_6699](https://discuss.codechef.com/user_avatar/discuss.codechef.com/tarun_6699/32/24644_2.png) [@tarun\_6699](https://discuss.codechef.com/u/tarun_6699)\
**Post date:** [March 23, 2020, 11:53am UTC](https://discuss.codechef.com/t/randchcl-editorial/57803/6 "2020-03-23T11:53:14Z")

</div>

I am unable to understand the expression given in the question please explain it.  
∑∑ gcd(A i,B j ).

---

<div class="post-metadata">

**Author:** ![sunil5798](https://discuss.codechef.com/user_avatar/discuss.codechef.com/sunil5798/32/24900_2.png) [@sunil5798](https://discuss.codechef.com/u/sunil5798)\
**Post date:** [March 23, 2020, 12:08pm UTC](https://discuss.codechef.com/t/randchcl-editorial/57803/7 "2020-03-23T12:08:35Z")

</div>

if anybody knows link to editorial for finding summation of gcd(Wi,Wj), please share.

---

<div class="post-metadata">

**Author:** ![tmwilliamlin](https://discuss.codechef.com/user_avatar/discuss.codechef.com/tmwilliamlin/32/9076_2.png) [@tmwilliamlin](https://discuss.codechef.com/u/tmwilliamlin)\
**Post date:** [March 23, 2020, 12:18pm UTC](https://discuss.codechef.com/t/randchcl-editorial/57803/8 "2020-03-23T12:18:07Z")

</div>

Just in case you don’t know, if you press explanation it shows the explanation for finding the summation of gcd(Wi, Wj)

---

<div class="post-metadata">

**Author:** ![ay2306](https://discuss.codechef.com/user_avatar/discuss.codechef.com/ay2306/32/34355_2.png) [@ay2306](https://discuss.codechef.com/u/ay2306)\
**Post date:** [March 23, 2020, 2:03pm UTC](https://discuss.codechef.com/t/randchcl-editorial/57803/9 "2020-03-23T14:03:19Z")

</div>

This question seemed like some very advanced mathematical problem but editorial made it seem like simple math. Great editorial.

---

<div class="post-metadata">

**Author:** ![divyansh15](https://discuss.codechef.com/user_avatar/discuss.codechef.com/divyansh15/32/12045_2.png) [@divyansh15](https://discuss.codechef.com/u/divyansh15)\
**Post date:** [April 2, 2020, 11:14am UTC](https://discuss.codechef.com/t/randchcl-editorial/57803/10 "2020-04-02T11:14:19Z")

</div>

First, we will calculate a frequency array cc of all the elements in WW. Then, we will calculate an array dd such that d\_id  
i  
​   
is the number of elements in WW which are multiples of ii. The pseudocode is shown below:

for i from 1 to MAX:  
j = i  
while j \<= MAX:  
d[i] += c[j]  
j += i  
The total time can be approximated by \sum\_{i = 1}^{N} \frac{N}{i}∑  
i=1  
N  
​

i  
N  
​   
, which is well-known to be equal to O(N \log N)O(NlogN) (approximate the sum with an integral).

Next, set d\_id  
i  
​   
to d\_i^2d  
i  
2  
​   
, so d\_id  
i  
​   
now represents the number of pairs of elements in WW such that both elements of the pair are multiples of ii.

Note that d\_id  
i  
​   
also represents the number of pairs such that the gcd of the first element and the second element is a multiple of ii. Next, we want to find e\_ie  
i  
​   
, which is the number of pairs such that the gcd of the first element and the second element is exactly ii. We can find e\_ie  
i  
​   
with complementary counting. We subtract all cases when the gcd isn’t exactly ii but is a multiple of ii:

for i from MAX to 1:  
e[i] = d[i]_d[i]  
j = 2_i  
while j \<= MAX:  
e[i] -= e[j]  
j += i  
The final sum of the gcd over all pairs can be found by summing up I \* e[I]

---

<div class="post-metadata">

**Author:** ![divyansh15](https://discuss.codechef.com/user_avatar/discuss.codechef.com/divyansh15/32/12045_2.png) [@divyansh15](https://discuss.codechef.com/u/divyansh15)\
**Post date:** [April 2, 2020, 11:15am UTC](https://discuss.codechef.com/t/randchcl-editorial/57803/11 "2020-04-02T11:15:04Z")

</div>

Written in editorial itself.

---

<div class="post-metadata">

**Author:** ![nemesis1](https://discuss.codechef.com/user_avatar/discuss.codechef.com/nemesis1/32/222565_2.png) [@nemesis1](https://discuss.codechef.com/u/nemesis1)\
**Post date:** [April 11, 2020, 9:21am UTC](https://discuss.codechef.com/t/randchcl-editorial/57803/12 "2020-04-11T09:21:35Z")

</div>

@tmwilliamlin @induber @ay2306  
why score is expected value of gcd(a[i],b[j])\*k^2?  
how does expected value term come from score expression ?

---

<div class="post-metadata">

**Author:** ![ay2306](https://discuss.codechef.com/user_avatar/discuss.codechef.com/ay2306/32/34355_2.png) [@ay2306](https://discuss.codechef.com/u/ay2306)\
**Post date:** [April 11, 2020, 10:13am UTC](https://discuss.codechef.com/t/randchcl-editorial/57803/14 "2020-04-11T10:13:58Z")

</div>

There are 2K chocolates chosen from N chocolates and written in two array and all could be choosen any number of time with equal probability then those. Thus for any value GCD(A\_i,B\_j) seriously have equal probability to be selected from sequence

Like if chocolates were C\_1,C\_2,...,C\_N then A\_i can be anything from C with equal probability same for B\_j.

Thus for any fixed k,  
Expected value of \sum\_{i=1}^{k}\sum\_{j=1}^{k}GCD(A\_i,B\_j) is \sum\_{i=1}^{k}\sum\_{j=1}^{k}E(GCD(A\_i,B\_j) )

E(GCD(A\_i,B\_j)) is equal as for all i and j as all (A\_i,B\_j) has equal probability to be any pair (x,y) as all are choosen randomly and independently

Therefore \sum\_{i=1}^{k}\sum\_{j=1}^{k}E(GCD(A\_i,B\_j) ) = k^2\*E(GCD(A\_i,B\_j) )

But is k is also not fixed, then ans = E(k^2)\*E(GCD(A\_i,B\_j))

I am not that good at math, so do tell me if I am wrong. 😅

---

<div class="post-metadata">

**Author:** ![nemesis1](https://discuss.codechef.com/user_avatar/discuss.codechef.com/nemesis1/32/222565_2.png) [@nemesis1](https://discuss.codechef.com/u/nemesis1)\
**Post date:** [April 11, 2020, 1:56pm UTC](https://discuss.codechef.com/t/randchcl-editorial/57803/15 "2020-04-11T13:56:39Z")

</div>

Thank you very much  
I really appreciate writing back

---

<div class="post-metadata">

**Author:** ![flyingkebab](https://discuss.codechef.com/user_avatar/discuss.codechef.com/flyingkebab/32/3653_2.png) [@flyingkebab](https://discuss.codechef.com/u/flyingkebab)\
**Post date:** [April 18, 2020, 1:29pm UTC](https://discuss.codechef.com/t/randchcl-editorial/57803/16 "2020-04-18T13:29:02Z")

</div>

Man, that wasn’t trivial at all, the UI should seriously improve xD