304 North Cardinal St.
Dorchester Center, MA 02124

Expected GCD CodeChef Solution

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
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
for i in range(q):

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);
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)
}
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){

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<>();
}
for(int i = 2; i < MXSIZE; i++){		//Store Factors
for(int j = i << 1; j < MXSIZE; j += 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.close();
}

StringTokenizer st;

}

String next() {
while (st == null || !st.hasMoreElements()) {
try{
}
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
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
for i in range(q):

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 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++)
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 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();
inputBuffer = new byte[MonoBufferSize];
}

{
if (bytesRead < 0) throw new FormatException();
inputIndex = 0;
inputBuffer[0] = (byte)EOL;
}

{
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);
}
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;
}

return g;
}

{
builder.Clear();
while (true)
{
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 f = BindingFlags.NonPublic | BindingFlags.Instance;
t.GetType().GetField("stack_size", f).SetValue(t, 32 * 1024 * 1024);
#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() {
nums := make([]int, n)
for i := 0; i < n; i++ {
}
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
}

return
}

a, b = res[0], res[1]
return
}

a, b, c = res[0], res[1], res[2]
return
}

res := make([]int, n)
x := 0
for i := 0; i < n; i++ {
for x < len(bs) && (bs[x] < '0' || bs[x] > '9') && bs[x] != '-' {
x++
}
}
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 {
}

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] {
}
}
}

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] {
ans = sub(ans, mul(prev[x], now))
newCoff := nCr(i/x, k)
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!