Expected GCD CodeChef Solution

Problem -Expected GCD CodeChef Solution

This website is dedicated for CodeChef solution where we will publish right solution of all your favourite CodeChef problems along with detailed explanatory of different competitive programming concepts and languages.
<<Previous CodeChef Problem Next Codechef Problem>>

Expected GCD CodeChef Solution in C++14

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
 
#define ll long long int
#define pb push_back
#define all(x) x.begin(),x.end()
#define Max 10000000000000000

template <typename T>
using ordered_set = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T>
using min_heap=priority_queue<T, vector<T>, greater<T>>;

ll ans[200007],mod=1000000007,fact_l[200007],fact[200007],val[200007],inv[200007];
vector<ll> d[200007];

ll bigmod(ll n,ll p){
	if(!p)  return 1;
	if(p%2) return (n*bigmod(n,p-1))%mod;
	ll x=bigmod(n,p/2);
	return (x*x)%mod;
}

int main()
{   
	ll q,k;
	scanf("%lli %lli",&q,&k);

	for(ll i=1;i<200007;i++){
		for(ll j=i;j<200007;j+=i){
			d[j].pb(i);
		}
	}

	for(ll i=1;i<200007;i++) inv[i]=bigmod(i,mod-2);

	for(ll i=0;i<200007;i++){
		if(i<k-1){
			fact_l[i]=0;
			continue;
		}
		if(i==k-1) fact_l[i]=1;
		else{
			fact_l[i]=(fact_l[i-1]*i)%mod;
			fact_l[i]=(fact_l[i]*inv[i-k+1])%mod;
		}
	}
	
	for(ll i=0;i<200007;i++){
		if(i<k){
			fact[i]=0;
			continue;
		}
		if(i==k) fact[i]=1;
		else{
			fact[i]=(fact[i-1]*(i-k))%mod;
			fact[i]=(fact[i]*inv[i])%mod;
		}
	}

	val[1]=1;
	for(ll i=2;i<200007;i++){
		vector<ll> temp;
		temp=d[i];
		ll p[temp.size()];

		ans[i]=ans[i-1];
		for(ll j=temp.size()-1;j>=0;j--){
			p[j]=0;
			ll v=temp[j];
			val[v]++;
			if(val[v]<k) continue;
			ll c=fact_l[val[v]-1];
			
			for(ll l=j+1;l<temp.size();l++){
				if(temp[l]%v) continue;
				c=c-p[l];
				if(c<0) c+=mod;
			}
			p[j]=c;
			c=(c*v)%mod;
			ans[i]=(ans[i]+c)%mod;
		}
	}

	while(q--){
		ll n;
		scanf("%lli",&n);
		ll v=fact[n];
		
		printf("%lli\n",(ans[n]*v)%mod);
	}
	

	return 0;
}

Expected GCD CodeChef Solution in PYTH 3


from sys import stdin, stdout


def power(n, k, mod):
    if k == 0:
        return 1
    x = 1
    while k > 1:
        if k % 2 == 0:
            n = n * n % mod
        else:
            x = n * x % mod
            n = n * n % mod
        k //= 2
    return n * x % mod


def solve():
    mod = 10 ** 9 + 7
    max_n = 200000
    totient = [None] * (max_n + 1)
    totient[1] = 1
    for i in range(2, max_n + 1):
        if not totient[i]:
            totient[i] = i - 1
            for j in range(2 * i, max_n + 1, i):
                if not totient[j]:
                    totient[j] = j
                totient[j] = (i - 1) * totient[j] // i
    q, k = list(map(int, stdin.readline().strip().split()))
    perm = [1] * (max_n + 1)
    perm_inv = [1] * (max_n + 1)
    for i in range(1, max_n + 1):
        perm[i] = perm[i - 1] * i
        perm[i] %= mod
        perm_inv[i] = power(perm[i], mod - 2, mod)
    comb = [0] * (max_n + 1)
    for i in range(k - 1, max_n + 1):
        comb[i] = perm[i] * perm_inv[k - 1] * perm_inv[i - k + 1]
        comb[i] %= mod
    results = [0] * (max_n + 1)
    for i in range(1, max_n + 1):
        for j in range(1, max_n // i + 1):
            results[i * j] += comb[j - 1] * totient[i]
    for i in range(k + 1, max_n + 1):
        results[i] += results[i - 1]
        results[i] %= mod
    for i in range(k, max_n + 1):
        total = perm[i] * perm_inv[k] * perm_inv[i - k]
        results[i] *= power(total, mod - 2, mod)
        results[i] %= mod
    answers = [0] * q
    for i in range(q):
        n = int(stdin.readline().strip())
        answers[i] = results[n]
    stdout.write('\n'.join(map(str, answers)))


solve()

Expected GCD CodeChef Solution in C

// EXPGCD

#include <stdio.h>
#include <math.h>

#define ll long long
#define gc getchar_unlocked
#define MOD 1000000007

int getn(){
  int n = 0, c = gc(), f = 1;
  while(c != '-' && (c < '0' || c > '9')) c = gc();
  if(c == '-') f = -1, c = gc();
  while(c >= '0' && c <= '9') n = (n<<3) + (n<<1) + c - '0', c = gc();
  return n * f;
}

int madd(int a, int b){ return ((a += b) >= MOD) ? a-MOD : a; }
int msub(int a, int b){ return ((a -= b) < 0) ? a+MOD : a; }
int mmul(int a, int b){ return (int)((ll)a * b % MOD); }
int gcde(int a, int b, int* x, int* y){
  if(!a){ *x = 0, *y = 1; return b; }
  int g,x1,y1;
  g = gcde(b % a, a, &x1, &y1);
  *x = y1 - (b / a) * x1, *y = x1;
  return g;
}
int minv(int a){
  int x,y;
  if(gcde(a, MOD, &x, &y) != 1)
    return -1;
  return (x % MOD + MOD) % MOD;
}
int mdiv(int a, int b){
  int inv = minv(b);
  if(inv == -1) inv /= 0;
  return mmul(inv, a);
}

void sort(int* a, int n){
  if(n < 2) return;
  int p = a[n>>1], *l = a, *r = a+n-1, t;
  while(l <= r){
    if(*l < p){ l++; continue; }
    if(*r > p){ r--; continue; }
    t = *l; *l++ = *r; *r-- = t;
  }
  sort(a, r-a+1), sort(l, a+n-l);
}

int c[200], d[200], f[200001], s[200001], t[200001];

int npk(int n, int k){ return mdiv(f[n], f[n-k]); }

int main(){
  int N,Q,K, i,j,k, n,n2,dn;

  for(f[0] = i = 1; i <= 200000; ++i)
    f[i] = mmul(f[i-1], i);

  Q = getn(), K = getn();
  s[1] = 0, t[1] = 0;
  for(i = 2; i <= 200000; ++i){
    s[i] = s[i-1], t[i] = t[i-1], dn = 0;
    for(j = 1, n = sqrt(i); j <= n; ++j){
      if(i % j) continue;
      d[dn++] = j;
      if(j != (n2 = i / j)) d[dn++] = n2;
    }

    sort(d, dn);
    for(j = 0; j < dn; ++j)
      c[j] = 0;
    for(j = dn-1; j >= 0; --j){
      if(d[j] == i || i/d[j] < K) continue;
      n = npk(i/d[j]-1, K-1);
      c[j] = madd(c[j], n);
      for(k = j-1; k >= 0; --k)
        if(d[j] % d[k] == 0) c[k] = msub(c[k], c[j]);
    }
    for(j = 0; j < dn; ++j)
      s[i] = madd(s[i], mmul(c[j], d[j])), t[i] = madd(t[i], c[j]);
  }
  for(i = 1; i <= 200000; ++i)
    if(!s[i]) t[i] = 1;

  while(Q--){
    N = getn();
    printf("%d\n", mdiv(s[N], t[N]));
  }
  return 0;
}

Expected GCD CodeChef Solution in JAVA

/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
	final static long mod = (long)1e9+7;
        static long[] fac;
     
        static long combi(int n, int m) {
            long ans = fac[n];
            ans *= power(fac[m], mod - 2, mod);
            ans %= mod;
            ans *= power(fac[n - m], mod - 2, mod);
            return ans %= mod;
        }
     
        static long power(long x, long y, long p){
            long res = 1;
            x %= p;
            while (y > 0) {
                if((y & 1)==1){
                    res *= x;
                    res %= p;
                }
                y >>= 1;
                x *= x;
                x %= p;
            }
            return res;
        }
     
    	public static void main(String[] args){
    		
    		FastReader s=new FastReader(System.in);
    		PrintWriter w=new PrintWriter(System.out);
     
    		int MXSIZE = 200001;
    		int t = s.nextInt(), k = s.nextInt();
    		long[] coprimes = new long[MXSIZE], ans = new long[MXSIZE], p = new long[MXSIZE], q = new long[MXSIZE];
            fac = new long[MXSIZE];
            fac[0] = 1;
            for(int i = 1; i < MXSIZE; i++){		//Calculate factorials
                fac[i] = fac[i - 1] * i;
                fac[i] %= mod;
            }
            ArrayList<Integer>[] factors = new ArrayList[MXSIZE];
            for(int i = 1; i < MXSIZE; i++){
                factors[i] = new ArrayList<>();
                factors[i].add(1);
            }
            for(int i = 2; i < MXSIZE; i++){		//Store Factors
                for(int j = i << 1; j < MXSIZE; j += i) {
                    factors[j].add(i);
                }
            }
            for(int i = k; i < MXSIZE; i++){		//Actual dp solution
                for(int f: factors[i]){	
                    coprimes[i] -= coprimes[i / f]; //Subtract sets whose gcd is NOT 1
                    coprimes[i] += mod;
                    coprimes[i] %= mod;
                }
                coprimes[i] += combi(i - 1, k - 1); //Adding all possible combitions. This is added at last because 1 is a factor, and i don't want it to get subtracted by  
                coprimes[i] %= mod;			 	   //itself in previous loop, which will result in its value becoming zero
                for(int f: factors[i]){
                    p[i] += coprimes[i / f] * f;		//Calculate p and q, p being the sum of gcd and q is total sets
                    q[i] += coprimes[i / f];		//Note although we are finding gcd of all permutations, we need not multiply factorial(k) as 
                    p[i] %= mod;					//it will be multiplied in both p and q, thus effectively cancelling out :)
                    q[i] %= mod;
                }
            }
            //Now coprime[i] contains total sets which have integer 'i' in it and have gcd zero
         	for(int i = k; i < MXSIZE; i++){
         		p[i] += p[i - 1];	//Calculate sum of all GCDs till i
         		q[i] += q[i - 1];	//Calculate sum of all sets till i
         		p[i] %= mod;
         		q[i] %= mod;
         		ans[i] = (p[i] * power(q[i], mod - 2, mod))%mod; //perform modular division
         	}
     
            while(t-->0){
            	w.println(ans[s.nextInt()]); //display the required answer
            }
     
    		w.close();
    	}
     
    	static class FastReader { 
            BufferedReader br; 
            StringTokenizer st; 
      
            public FastReader(InputStream i) { 
                br = new BufferedReader(new InputStreamReader(i)); 
            } 
      
            String next() { 
                while (st == null || !st.hasMoreElements()) { 
                    try{ 
                        st = new StringTokenizer(br.readLine()); 
                    } 
                    catch (IOException  e) { 
                        e.printStackTrace(); 
                    } 
                } 
                return st.nextToken(); 
            } 
      
            int nextInt() { 
                return Integer.parseInt(next()); 
            } 
     
        } 
    }

Expected GCD CodeChef Solution in PYPY 3

from sys import stdin, stdout


def power(n, k, mod):
    if k == 0:
        return 1
    x = 1
    while k > 1:
        if k % 2 == 0:
            n = n * n % mod
        else:
            x = n * x % mod
            n = n * n % mod
        k //= 2
    return n * x % mod


def solve():
    mod = 10 ** 9 + 7
    max_n = 200000
    totient = [None] * (max_n + 1)
    totient[1] = 1
    for i in range(2, max_n + 1):
        if not totient[i]:
            totient[i] = i - 1
            for j in range(2 * i, max_n + 1, i):
                if not totient[j]:
                    totient[j] = j
                totient[j] = (i - 1) * totient[j] // i
    q, k = list(map(int, stdin.readline().strip().split()))
    perm = [1] * (max_n + 1)
    perm_inv = [1] * (max_n + 1)
    for i in range(1, max_n + 1):
        perm[i] = perm[i - 1] * i
        perm[i] %= mod
        perm_inv[i] = power(perm[i], mod - 2, mod)
    comb = [0] * (max_n + 1)
    for i in range(k - 1, max_n + 1):
        comb[i] = perm[i] * perm_inv[k - 1] * perm_inv[i - k + 1]
        comb[i] %= mod
    results = [0] * (max_n + 1)
    for i in range(1, max_n + 1):
        for j in range(1, max_n // i + 1):
            results[i * j] += comb[j - 1] * totient[i]
    for i in range(k + 1, max_n + 1):
        results[i] += results[i - 1]
        results[i] %= mod
    for i in range(k, max_n + 1):
        results[i] *= power(perm[i] * perm_inv[k] * perm_inv[i - k], mod - 2, mod)
        results[i] %= mod
    answers = [0] * q
    for i in range(q):
        n = int(stdin.readline().strip())
        answers[i] = results[n]
    stdout.write('\n'.join(map(str, answers)))


solve()

Expected GCD CodeChef Solution in C#

#region Usings
using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Reflection;
using System.Runtime.CompilerServices;
using System.Text;
using System.Threading;
using static System.Array;
using static System.Math;

// ReSharper disable InconsistentNaming
#pragma warning disable CS0675
#endregion

partial class Solution
{
	#region Variables
	const int MOD = 1000000007;
	const int FactCache = 200001;
	#endregion

	int M, K, N;
	int[] Q;

	int[][] divisors;

	long InclusionExclusion(long[] buffer, int d)
	{
		return 0;
	}

	public void Solve()
	{
		M = Ni();
		K = Ni();
		Q = Ni(M);

		N = Q.Max() + 1;

		var mobius = MobiusTable(N);
		divisors = DivisorsUpTo(N);

		var results = new long[N];
		var tallies = new long[N];
		var buffer = new long[N];
		for (int n = K; n < N; n++)
		{
			var divs = divisors[n];

			Clear(buffer, 0, divs.Length);

			for (int id = divs.Length - 1; id >= 0; id--)
			{
				var d = divs[id];
				int count = n / d;
				if (count < K) break;
				buffer[id] = Fact(count - 1, K - 1); // * K % MOD;
			}

			long result = 0;
			long tally = 0;

			for (int id = 0; id < divs.Length; id++)
			{
				var d = divs[id];
				long count = buffer[id];
				if (count == 0)
					continue;

				for (int id2 = id + 1; id2 < divs.Length; id2++)
				{
					if (d % divs[id2] == 0)
					{
						var count2 = buffer[id2] - count;
						if (count2 < 0) count2 += MOD;
						buffer[id2] = count2;
					}
				}

				tally = (tally + count) % MOD;
				result = (result + count % MOD * d) % MOD;
			}


			//for (int id = divs.Length-1; id >= 0; id--)
			//{
			//	var d = divs[id];
			//	long count = 0;

			//	for (int id2 = 0; id2 <= id; id2++)
			//	{
			//		var d2 = divs[id2];
			//		if (d2 % d == 0)
			//			count += buffer[id2] * mobius[d2];
			//	}

			//	count = Abs(count);
			//	if (count != 0)
			//	{
			//		tally = (tally + count) % MOD;
			//		result = (result + count % MOD * d) % MOD;
			//	}
			//}

			tallies[n] = Fix(tallies[n - 1] + tally);
			results[n] = Fix(results[n - 1] + result);
		}

		foreach (var n in Q)
		{
			if (n < K)
			{
				WriteLine(0);
				continue;
			}

			long result = Fix(results[n] * K % MOD);
			long div = Fact(n, K) ;
			//Debug.Assert(div == tallies[n]);
			result = Div(result, div);
			WriteLine(result);
		}
	}

	public static int[][] DivisorsUpTo(int n)
	{
		n++;
		var counts = new short[n];
		var divisors = new int[n][];
		for (int i = 1; i < n; i++)
		{
			for (int j = i; j < n; j += i)
				counts[j]++;
		}

		for (int i = 1; i < n; i++)
			divisors[i] = new int[counts[i]];

		for (int i = 1; i < n; i++)
		{
			for (int j = i; j < n; j += i)
				divisors[j][--counts[j]] = i;
		}
		return divisors;
	}

	public static sbyte[] MobiusTable(int limit)
	{
		var sq = (int)Sqrt(limit);

		var prime = new BitArray(limit) { [2] = true };
		for (int i = 3; i < limit; i += 2)
			prime[i] = true;

		for (int i = 3; i < sq; i += 2)
			if (prime[i])
				for (int j = i * i; j < limit; j += 2 * i)
					prime[j] = false;

		var mobius = new sbyte[limit];
		for (int i = 0; i < limit; i++)
			mobius[i] = 1;

		for (int p = 2; p < limit; p++)
		{
			if (!prime[p]) continue;
			for (int q = p; q < limit; q += p)
				mobius[q] *= -1;
			for (long r = p * 1L * p, q = r; q < limit; q += r)
				mobius[q] = 0;
		}

		return mobius;
	}



	#region Library
	#region Mod Math

	static int[] _inverse;
	static long Inverse(long n)
	{
		long result;

		if (_inverse == null)
			_inverse = new int[1000];

		if (n >= 0 && n < _inverse.Length && (result = _inverse[n]) != 0)
			return result - 1;

		result = InverseDirect((int)n);
		if (n >= 0 && n < _inverse.Length)
			_inverse[n] = (int)(result + 1);
		return result;
	}

	public static int InverseDirect(int a, int mod = MOD)
	{
		int b = mod, p = 1, q = 0;
		while (b > 0)
		{
			int c = a / b, d = a;
			a = b;
			b = d % b;
			d = p;
			p = q;
			q = d - c * q;
		}
		return p < 0 ? p + mod : p;
	}

	static long Mult(long left, long right) =>
		(left * right) % MOD;

	static long Div(long left, long divisor) =>
		left * Inverse(divisor) % MOD;

	static long Add(long x, long y) =>
		(x += y) >= MOD ? x - MOD : x;

	static long Subtract(long x, long y) => (x -= y) < 0 ? x + MOD : x;

	static long Fix(long n) => (n %= MOD) >= 0 ? n : n + MOD;

	static long ModPow(long n, long p, long mod = MOD)
	{
		long b = n;
		long result = 1;
		while (p != 0)
		{
			if ((p & 1) != 0)
				result = (result * b) % mod;
			p >>= 1;
			b = (b * b) % mod;
		}
		return result;
	}

	static List<long> _fact;

	static long Fact(int n)
	{
		if (_fact == null) _fact = new List<long>(FactCache) { 1 };
		for (int i = _fact.Count; i <= n; i++)
			_fact.Add(Mult(_fact[i - 1], i));
		return _fact[n];
	}

	static long[] _ifact = new long[0];
	static long InverseFact(int n)
	{
		long result;
		if (n < _ifact.Length && (result = _ifact[n]) != 0)
			return result;

		var inv = Inverse(Fact(n));
		if (n >= _ifact.Length) Resize(ref _ifact, _fact.Capacity);
		_ifact[n] = inv;
		return inv;
	}

	static long Fact(int n, int m)
	{
		if (m > n) return 0;
		var fact = Fact(n);
		if (m < n) fact = fact * InverseFact(n - m) % MOD;
		return fact;
	}

	static long Comb(int n, int k)
	{
		if (k <= 1) return k == 1 ? n : k == 0 ? 1 : 0;
		return Mult(Mult(Fact(n), InverseFact(k)), InverseFact(n - k));
	}

	public static long Combinations(long n, int k)
	{
		if (k <= 0) return k == 0 ? 1 : 0;  // Note: n<0 -> 0 unless k=0
		if (k + k > n) return Combinations(n, (int)(n - k));

		var result = InverseFact(k);
		for (long i = n - k + 1; i <= n; i++) result = result * i % MOD;
		return result;
	}
	#endregion

	#region Common
	partial void TestData();

	static void Swap<T>(ref T a, ref T b)
	{
		var tmp = a;
		a = b;
		b = tmp;
	}

	static int Bound<T>(T[] array, T value, bool upper = false)
		where T : IComparable<T>
	{
		int left = 0;
		int right = array.Length - 1;

		while (left <= right)
		{
			int mid = left + (right - left >> 1);
			int cmp = value.CompareTo(array[mid]);
			if (cmp > 0 || cmp == 0 && upper)
				left = mid + 1;
			else
				right = mid - 1;
		}
		return left;
	}

	public static int Gcd(int n, int m)
	{
		while (true)
		{
			if (m == 0) return n >= 0 ? n : -n;
			n %= m;
			if (n == 0) return m >= 0 ? m : -m;
			m %= n;
		}
	}

	[MethodImpl(MethodImplOptions.AggressiveInlining)]
	static unsafe int Log2(long value)
	{
		double f = unchecked((ulong)value); // +.5 -> -1 for zero
		return (((int*)&f)[1] >> 20) - 1023;
	}

	[MethodImpl(MethodImplOptions.AggressiveInlining)]
	static int BitCount(long y)
	{
		var x = unchecked((ulong)y);
		x -= (x >> 1) & 0x5555555555555555;
		x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333);
		x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f;
		return unchecked((int)((x * 0x0101010101010101) >> 56));
	}

	[MethodImpl(MethodImplOptions.AggressiveInlining)]
	static int HighestOneBit(int n) => n != 0 ? 1 << Log2(n) : 0;
	/*static unsafe int HighestOneBit(int x) // sometimes doesn't work
	{
		double f = unchecked((uint)x);
        return unchecked(1 << (((int*)&f)[1] >> 20) - 1023 & ~((x - 1 & -x - 1) >> 31));
	}*/

	[MethodImpl(MethodImplOptions.AggressiveInlining)]
	static unsafe long HighestOneBit(long x)
	{
		double f = unchecked((ulong)x);
		return unchecked(1L << (((int*)&f)[1] >> 20) - 1023 & ~(x - 1 >> 63 & -x - 1 >> 63));
	}
	#endregion

	#region Fast IO
	#region  Input
	static Stream inputStream;
	static int inputIndex, bytesRead;
	static byte[] inputBuffer;
	static StringBuilder builder;
	const int MonoBufferSize = 4096;
	const char EOL = (char)10, DASH = (char)45, ZERO = (char)48;

	static void InitInput(Stream input = null, int stringCapacity = 16)
	{
		builder = new StringBuilder(stringCapacity);
		inputStream = input ?? Console.OpenStandardInput();
		inputIndex = bytesRead = 0;
		inputBuffer = new byte[MonoBufferSize];
	}

	static void ReadMore()
	{
		if (bytesRead < 0) throw new FormatException();
		inputIndex = 0;
		bytesRead = inputStream.Read(inputBuffer, 0, inputBuffer.Length);
		if (bytesRead > 0) return;
		bytesRead = -1;
		inputBuffer[0] = (byte)EOL;
	}

	static int Read()
	{
		if (inputIndex >= bytesRead) ReadMore();
		return inputBuffer[inputIndex++];
	}

	static T[] Na<T>(int n, Func<T> func, int z = 0)
	{
		n += z;
		var list = new T[n];
		for (int i = z; i < n; i++) list[i] = func();
		return list;
	}

	static int[] Ni(int n, int z = 0) => Na(n, Ni, z);

	static long[] Nl(int n, int z = 0) => Na(n, Nl, z);

	static string[] Ns(int n, int z = 0) => Na(n, Ns, z);

	static int Ni() => checked((int)Nl());

	static long Nl()
	{
		var c = SkipSpaces();
		bool neg = c == DASH;
		if (neg) { c = Read(); }

		long number = c - ZERO;
		while (true)
		{
			var d = Read() - ZERO;
			if (unchecked((uint)d > 9)) break;
			number = number * 10 + d;
			if (number < 0) throw new FormatException();
		}
		return neg ? -number : number;
	}

	static char[] Nc(int n)
	{
		var list = new char[n];
		for (int i = 0, c = SkipSpaces(); i < n; i++, c = Read()) list[i] = (char)c;
		return list;
	}

	static string Ns()
	{
		var c = SkipSpaces();
		builder.Clear();
		while (true)
		{
			if (unchecked((uint)c - 33 >= (127 - 33))) break;
			builder.Append((char)c);
			c = Read();
		}
		return builder.ToString();
	}

	static int SkipSpaces()
	{
		int c;
		do c = Read(); while (unchecked((uint)c - 33 >= (127 - 33)));
		return c;
	}

	static List<int>[] NewGraph(int n, int m = 0, int off = 0)
	{
		n += 1 + off;
		var g = new List<int>[n];
		for (int i = 0; i < n; i++)
			g[i] = new List<int>();

		for (int i = 0; i < m; i++)
		{
			int u = Ni() + off, v = Ni() + off;
			g[u].Add(v);
			g[v].Add(u);
		}

		return g;
	}

	static string ReadLine()
	{
		builder.Clear();
		while (true)
		{
			int c = Read();
			if (c < 32) { if (c == 10 || c <= 0) break; continue; }
			builder.Append((char)c);
		}
		return builder.ToString();
	}
	#endregion

	#region Output
	static Stream outputStream;
	static byte[] outputBuffer;
	static int outputIndex;

	static void InitOutput(Stream output = null)
	{
		outputStream = output ?? Console.OpenStandardOutput();
		outputIndex = 0;
		outputBuffer = new byte[65535];
	}

	static void WriteLine(object obj = null)
	{
		Write(obj);
		Write(EOL);
	}

	static void WriteLine(long number)
	{
		Write(number);
		Write(EOL);
	}

	static void Write(long signedNumber)
	{
		ulong number = unchecked((ulong)signedNumber);
		if (signedNumber < 0)
		{
			Write(DASH);
			number = unchecked((ulong)(-signedNumber));
		}

		Reserve(20 + 1); // 20 digits + 1 extra for sign
		int left = outputIndex;
		do
		{
			outputBuffer[outputIndex++] = (byte)(ZERO + number % 10);
			number /= 10;
		}
		while (number > 0);

		int right = outputIndex - 1;
		while (left < right)
		{
			byte tmp = outputBuffer[left];
			outputBuffer[left++] = outputBuffer[right];
			outputBuffer[right--] = tmp;
		}
	}

	static void Write(object obj)
	{
		if (obj == null) return;

		var s = obj.ToString();
		Reserve(s.Length);
		for (int i = 0; i < s.Length; i++)
			outputBuffer[outputIndex++] = (byte)s[i];
	}

	static void Write(char c)
	{
		Reserve(1);
		outputBuffer[outputIndex++] = (byte)c;
	}

	static void Write(byte[] array, int count)
	{
		Reserve(count);
		Copy(array, 0, outputBuffer, outputIndex, count);
		outputIndex += count;
	}

	static void Reserve(int n)
	{
		if (outputIndex + n <= outputBuffer.Length)
			return;

		Dump();
		if (n > outputBuffer.Length)
			Resize(ref outputBuffer, Max(outputBuffer.Length * 2, n));
	}

	static void Dump()
	{
		outputStream.Write(outputBuffer, 0, outputIndex);
		outputIndex = 0;
	}

	static void Flush()
	{
		Dump();
		outputStream.Flush();
	}

	#endregion
	#endregion

	#region Main

	public static void Main()
	{
		AppDomain.CurrentDomain.UnhandledException += (sender, arg) =>
		{
			Flush();
			var e = (Exception)arg.ExceptionObject;
			Console.Error.WriteLine(e);
			var line = new StackTrace(e, true).GetFrames()
				.Select(x => x.GetFileLineNumber()).FirstOrDefault(x => x != 0);
			var wait = line % 300 * 10 + 5;
			var process = Process.GetCurrentProcess();
			while (process.TotalProcessorTime.TotalMilliseconds > wait && wait < 3000) wait += 1000;
			while (process.TotalProcessorTime.TotalMilliseconds < Min(wait, 3000)) ;
			Environment.Exit(1);
		};

		InitInput(Console.OpenStandardInput());
		InitOutput(Console.OpenStandardOutput());
#if __MonoCS__ && !C7
        var thread = new System.Threading.Thread(()=>new Solution().Solve());
        var f = BindingFlags.NonPublic | BindingFlags.Instance;
        var t = thread.GetType().GetField("internal_thread", f).GetValue(thread);
        t.GetType().GetField("stack_size", f).SetValue(t, 32 * 1024 * 1024);
        thread.Start();
        thread.Join();
#else
		new Solution().Solve();
#endif
		Flush();
		Console.Error.WriteLine(Process.GetCurrentProcess().TotalProcessorTime);
	}
	#endregion
	#endregion
}

Expected GCD CodeChef Solution in GO

package main

import (
	"bufio"
	"bytes"
	"fmt"
	"os"
)

func main() {
	reader := bufio.NewReader(os.Stdin)
	n, k := readTwoNums(reader)
	nums := make([]int, n)
	for i := 0; i < n; i++ {
		nums[i] = readNum(reader)
	}
	res := solve(k, nums)
	var buf bytes.Buffer
	for _, ans := range res {
		buf.WriteString(fmt.Sprintf("%d\n", ans))
	}

	fmt.Print(buf.String())
}

func readInt(bytes []byte, from int, val *int) int {
	i := from
	sign := 1
	if bytes[i] == '-' {
		sign = -1
		i++
	}
	tmp := 0
	for i < len(bytes) && bytes[i] >= '0' && bytes[i] <= '9' {
		tmp = tmp*10 + int(bytes[i]-'0')
		i++
	}
	*val = tmp * sign
	return i
}

func readNum(reader *bufio.Reader) (a int) {
	bs, _ := reader.ReadBytes('\n')
	readInt(bs, 0, &a)
	return
}

func readTwoNums(reader *bufio.Reader) (a int, b int) {
	res := readNNums(reader, 2)
	a, b = res[0], res[1]
	return
}

func readThreeNums(reader *bufio.Reader) (a int, b int, c int) {
	res := readNNums(reader, 3)
	a, b, c = res[0], res[1], res[2]
	return
}

func readNNums(reader *bufio.Reader, n int) []int {
	res := make([]int, n)
	x := 0
	bs, _ := reader.ReadBytes('\n')
	for i := 0; i < n; i++ {
		for x < len(bs) && (bs[x] < '0' || bs[x] > '9') && bs[x] != '-' {
			x++
		}
		x = readInt(bs, x, &res[i])
	}
	return res
}

func readUint64(bytes []byte, from int, val *uint64) int {
	i := from

	var tmp uint64
	for i < len(bytes) && bytes[i] >= '0' && bytes[i] <= '9' {
		tmp = tmp*10 + uint64(bytes[i]-'0')
		i++
	}
	*val = tmp

	return i
}

const MOD = 1000000007
const MAX_N = 200010

var F [MAX_N]int64
var I [MAX_N]int64
var sum [MAX_N]int64
var mobius [MAX_N]int64
var divs [][]int

func pow(a, b int64) int64 {
	var r int64 = 1
	for b > 0 {
		if b&1 == 1 {
			r = (r * a) % MOD
		}
		a = (a * a) % MOD
		b >>= 1
	}
	return r
}

func mul(a, b int64) int64 {
	a *= b
	a %= MOD
	return a
}

func add(a, b int64) int64 {
	a += b
	if a >= MOD {
		a -= MOD
	}
	return a
}

func sub(a, b int64) int64 {
	return add(a, MOD-b)
}

func init() {
	F[0] = 1
	for i := 1; i < MAX_N; i++ {
		F[i] = int64(i) * F[i-1] % MOD
	}

	I[MAX_N-1] = pow(F[MAX_N-1], MOD-2)

	for i := MAX_N - 2; i >= 0; i-- {
		I[i] = int64(i+1) * I[i+1] % MOD
	}

	for i := 0; i < MAX_N; i++ {
		mobius[i] = 1
	}
	mobius[1] = 0

	set := make([]bool, MAX_N)

	for i := 2; i < MAX_N; i++ {
		if !set[i] {

			i2 := int64(i) * int64(i)
			for j := i; j < MAX_N; j += i {
				set[j] = true
				// *= -1
				mobius[j] = mul(mobius[j], MOD-1)
				if int64(j)%(i2) == 0 {
					mobius[j] = 0
				}
			}
		}
	}

	divs = make([][]int, MAX_N)
	for i := 1; i < MAX_N; i++ {
		divs[i] = make([]int, 0, 2)
	}
	for i := 1; i < MAX_N; i++ {
		for j := i; j < MAX_N; j += i {
			divs[j] = append(divs[j], i)
		}
	}

	for i := 1; i < MAX_N; i++ {
		for _, x := range divs[i] {
			sum[i] = add(sum[i], mul(mobius[x], int64(i/x)))
		}
	}
}

func nCr(n, r int) int64 {
	if r < 0 || n < r {
		return 0
	}
	return mul(F[n], mul(I[r], I[n-r]))
}

func solve(k int, nums []int) []int {
	res := make([]int64, 200001)
	prev := make([]int64, 200001)
	var ans int64
	for i := k; i <= 200000; i++ {
		for _, x := range divs[i] {
			now := add(int64(x), sum[x])
			ans = sub(ans, mul(prev[x], now))
			newCoff := nCr(i/x, k)
			ans = add(ans, mul(newCoff, now))
			prev[x] = newCoff
		}
		den := mul(I[i], mul(F[k], F[i-k]))
		res[i] = mul(den, ans)
	}

	ret := make([]int, len(nums))

	for i, n := range nums {
		ret[i] = int(res[n])
	}

	return ret
}
Expected GCD CodeChef Solution Review:

In our experience, we suggest you solve this Expected GCD CodeChef Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Expected GCD CodeChef Solution.

Find on CodeChef

Conclusion:

I hope this Expected GCD CodeChef Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Programming Language in a business context; there are no prerequisites.

Keep Learning!

More Coding Solutions >>

Cognitive Class Answer

CodeChef Solution

Microsoft Learn

Leave a Reply

Your email address will not be published. Required fields are marked *