304 North Cardinal St.
Dorchester Center, MA 02124

# KBG and GN-Theory CodeChef Solution

## KBG and GN-Theory CodeChef Solution in C++17

``````#include <iostream>
#include <unordered_set>
#include <vector>
#include <queue>
#include <algorithm>
#include <unordered_map>
#include <cstring>
#include <map>
#define int long long
#define endl "\n"
using namespace std;

const int N = 1e5 + 5;
int lpf[N];

void pre() {
for(int i = 2; i < N; ++i) {
if(lpf[i] == 0) {
for(int j = i; j < N; j += i) {
lpf[j] = i;
}
}
}
}

void solve(){
int n, q; cin >> n >> q;
for(int i = 0; i < q; i++){
int u, v; cin >> u >> v;
int k = 0;
unordered_map<int, int> mp;
int tempu = u;
int tempv = v;
while(tempu != 1){
int y = lpf[tempu];
while(tempu % y == 0){
tempu /= y;
mp[y]++;
}
}
while(tempv != 1){
int y = lpf[tempv];
while(tempv % y == 0){
tempv /= y;
mp[y]--;
}
}
int ans = 0;
for(auto &it : mp){
ans += it.first * abs(it.second);
}
cout << ans << endl;
}
}

int32_t main(){
cin.tie(0);
ios_base::sync_with_stdio(0);
int t = 1;
cin >> t;
pre();
while(t--) solve();
return 0;
}``````

## KBG and GN-Theory CodeChef Solution in C++14

``````#include <bits/stdc++.h>
#define int long long
using namespace std;

int x=0,f=1;
char ch=getchar();
while(ch<48||ch>57) {
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>=48&&ch<=57) {
x=(x<<3)+(x<<1)+(ch^48);
ch=getchar();
}
return x*f;

}

int T,n,q;

int work(int x) {

int cnt=0;
for(int i=2;i*i<=x;i++) {

if(x%i==0) {

while(x%i==0) {

cnt+=i;
x/=i;

}

}

}
if(x>1) cnt+=x;
return cnt;

}

signed main() {

while(T--) {

while(q--) {

int gcd=__gcd(x,y);
if(x<y) swap(x,y);
x/=gcd;
y/=gcd;
int ans=work(x)+work(y);
printf("%lld\n",ans);

}

}

return 0;
}``````

## KBG and GN-Theory CodeChef Solution in PYTH 3

``````def hel2(x,y):
if x == y:
return 0
l = []
for i in range(1,int(x**0.5)+1):
if x%i == 0:
l.append(i)
l.append(x//i)
if i*i == x:
l.pop()
l.sort(reverse=True)
#print(l)
cnt = 0
prev = x
for i in range(1,len(l)):
if prev%l[i] == 0 and l[i]%y == 0:
cnt += prev//l[i]
#print(l[i])
#print(cnt,prev)
prev = l[i]
if l[i] == y:
break
return cnt

def gcd(x,y):
if x%y == 0:
return y
return gcd(y,x%y)

def fun(n,u,v):
g = gcd(u,v)
res1 = hel2(u,g)
#print("res1 " + str(res1))
res2 = hel2(v,g)
#print("res2 " + str(res2))
res = res1 + res2
return res

for _ in range(int(input())):
n,q = map(int,input().split())
for _ in range(q):
u,v = map(int,input().split())
print(fun(n,u,v))
``````

## KBG and GN-Theory CodeChef Solution in JAVA

``````
import java.io.IOException;
import java.util.*;

class Codechef {

static long mod = 1000000007;
static FastScanner scanner;
static int INF = Integer.MAX_VALUE;
static ArrayList<Integer> primes = new ArrayList<>();
static int MAX_ARRAY = 1000001;
static int n;
static int q;

static final StringBuilder result = new StringBuilder();

public static void main(String[] args) {
scanner = new FastScanner();
int T = scanner.nextInt();
for (int t = 0; t < T; t++) {
solve(t + 1);
}
System.out.println(result);
}

static void solve(int t) {
n = scanner.nextInt();
q = scanner.nextInt();
for(int i = 0; i < q; i++){
int u = scanner.nextInt();
int v = scanner.nextInt();
if(u > v){
int temp = u;
u = v;
v = temp;
}
// u < v
if(v % u == 0){
int ans = minDist(v, u);
result.append(ans+"\n");
}
else{
int gcd = gcd(u, v);
int ans = minDist(v, gcd) + minDist(u, gcd);
result.append(ans+"\n");
}
}
}

static int minDist(int cur, int dest){
// System.out.println(cur+" , "+dest);
if(cur == dest)
return 0;
if(cur < dest)
return INF;
if(cur % dest != 0)
return INF;
int minRoute = cur/dest;
for(int i = 2; (i * i) <= cur; i++){
if(cur % i == 0){
int value = minDist(cur / i, dest);
if(value != INF) {
int newDist = i + value;
// System.out.println(" Cur = " + cur + " dest = " + dest + " , to = " + (cur / i) + " by dist = " + i + "new Dist = " + newDist);
minRoute = Math.min(minRoute, newDist);
// System.out.println("Min Route = " + minRoute);
}
}
}
return minRoute;
}

static class Pair{
char x;
int f;
public Pair(char x, int f){
this.x = x;
this.f = f;
}
@Override
public String toString(){
return "(char = "+x+", frequency = "+f+")";
}
}

static int gcd (int a, int b){
if(b == 0) return a;
return gcd(b, a%b);
}

static long gcd_long (long a, long b){
if(b == 0) return a;
return gcd_long(b, a%b);
}

static boolean isPrime(int x){
if(x < 2) return false;
if(x == 2) return true;
if(x % 2 == 0) return true;
for(int i = 3; (i * i) <= x; i++){
if(x % i == 0) return false;
}
return true;
}

static class WithIdx implements Comparable<WithIdx> {
long val, idx;

public WithIdx(long val, long idx) {
this.val = val;
this.idx = idx;
}

@Override
public int compareTo(WithIdx o) {
if (val == o.val) {
return Long.compare(idx, o.idx);
}
return Long.compare(val, o.val);
}
}

public static class FastScanner {
StringTokenizer st;

public FastScanner() {
}

String nextToken() {
while (st == null || !st.hasMoreElements()) {
try {
} catch (IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
return st.nextToken();
}

String nextLine() {
try {
} catch (Exception e) {
e.printStackTrace();
throw new RuntimeException();
}
}

int nextInt() {
return Integer.parseInt(nextToken());
}

long nextLong() {
return Long.parseLong(nextToken());
}

double nextDouble() {
return Double.parseDouble(nextToken());
}

int[] nextIntArray(int n) {
int[] res = new int[n];
for (int i = 0; i < n; i++) res[i] = nextInt();
return res;
}

long[] nextLongArray(int n) {
long[] res = new long[n];
for (int i = 0; i < n; i++) res[i] = nextLong();
return res;
}

String[] nextStringArray(int n) {
String[] res = new String[n];
for (int i = 0; i < n; i++) res[i] = nextToken();
return res;
}
}

static class PrefixSums {
long[] sums;

public PrefixSums(long[] sums) {
this.sums = sums;
}

public long sum(int fromInclusive, int toExclusive) {
if (fromInclusive > toExclusive) throw new IllegalArgumentException("Wrong value");
return sums[toExclusive] - sums[fromInclusive];
}

public static PrefixSums of(int[] ar) {
long[] sums = new long[ar.length + 1];
for (int i = 1; i <= ar.length; i++) {
sums[i] = sums[i - 1] + ar[i - 1];
}
return new PrefixSums(sums);
}

public static PrefixSums of(long[] ar) {
long[] sums = new long[ar.length + 1];
for (int i = 1; i <= ar.length; i++) {
sums[i] = sums[i - 1] + ar[i - 1];
}
return new PrefixSums(sums);
}
}

static void sort(int[] ar) {
for (int i = ar.length - 1; i > 0; i--) {
int index = rnd.nextInt(i + 1);
// Simple swap
int a = ar[index];
ar[index] = ar[i];
ar[i] = a;
}
Arrays.sort(ar);
}

static void reverse(int[] arr) {
int last = arr.length / 2;
for (int i = 0; i < last; i++) {
int tmp = arr[i];
arr[i] = arr[arr.length - 1 - i];
arr[arr.length - 1 - i] = tmp;
}
}

static void sort(long[] ar) {
for (int i = ar.length - 1; i > 0; i--) {
int index = rnd.nextInt(i + 1);
// Simple swap
long a = ar[index];
ar[index] = ar[i];
ar[i] = a;
}
Arrays.sort(ar);
}
}

static class MathUtils {
static long[] FIRST_PRIMES = {
2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
73, 79, 83, 89, 97, 101, 103, 107, 109, 113,
127, 131, 137, 139, 149, 151, 157, 163, 167, 173,
179, 181, 191, 193, 197, 199, 211, 223, 227, 229,
233, 239, 241, 251, 257, 263, 269, 271, 277, 281,
283, 293, 307, 311, 313, 317, 331, 337, 347, 349,
353, 359, 367, 373, 379, 383, 389, 397, 401, 409,
419, 421, 431, 433, 439, 443, 449, 457, 461, 463,
467, 479, 487, 491, 499, 503, 509, 521, 523, 541,
547, 557, 563, 569, 571, 577, 587, 593, 599, 601,
607, 613, 617, 619, 631, 641, 643, 647, 653, 659,
661, 673, 677, 683, 691, 701, 709, 719, 727, 733,
739, 743, 751, 757, 761, 769, 773, 787, 797, 809,
811, 821, 823, 827, 829, 839, 853, 857, 859, 863,
877, 881, 883, 887, 907, 911, 919, 929, 937, 941,
947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013,
1019, 1021, 1031, 1033, 1039, 1049, 1051};

static long[] primes(int to) {
long[] all = new long[to + 1];
long[] primes = new long[to + 1];
all[1] = 1;
int primesLength = 0;
for (int i = 2; i <= to; i++) {
if (all[i] == 0) {
primes[primesLength++] = i;
all[i] = i;
}
for (int j = 0; j < primesLength && i * primes[j] <= to && all[i] >= primes[j];
j++) {
all[(int) (i * primes[j])] = primes[j];
}
}
return Arrays.copyOf(primes, primesLength);
}

static long modpow(long b, long e, long m) {
long result = 1;

while (e > 0) {
if ((e & 1) == 1) {
/* multiply in this bit's contribution while using modulus to keep
* result small */
result = (result * b) % m;
}
b = (b * b) % m;
e >>= 1;
}

return result;
}

static long submod(long x, long y, long m) {
return (x - y + m) % m;
}

static long modInverse(long a, long m) {
long g = gcdF(a, m);
if (g != 1) {
throw new IllegalArgumentException("Inverse doesn't exist");
} else {
// If a and m are relatively prime, then modulo
// inverse is a^(m-2) mode m
return modpow(a, m - 2, m);
}
}

static public long gcdF(long a, long b) {
while (b != 0) {
long na = b;
long nb = a % b;
a = na;
b = nb;
}
return a;
}
}
}``````

## KBG and GN-Theory CodeChef Solution in PYPY 3

``````from sys import stdin

from math import ceil, floor, sqrt, log2, gcd
from heapq import heappush, heappop
from collections import deque
from functools import lru_cache
from bisect import bisect_left, bisect_right

def rl(t = int):
return list(map(t, input().split()))

T = int(input())

#     4
#     | \
# 3 - 1 - 2
#     |
#     5
LIM = 10**5
primes = set(range(2, LIM + 1))
for i in range(2, LIM + 1):
if i in primes:
j = i * 2
while j <= LIM:
if j in primes:
primes.remove(j)
j += i

pfs = [{} for _ in range(LIM + 1)]
for prime in primes:
v = prime
while v <= LIM:
cur = v
while cur <= LIM:
pfs[cur][prime] = pfs[cur].get(prime, 0) +1
cur += v
v *= prime

for t in range(1, T + 1):
n, q = rl()
# u = p1 * p2 * p3
# v = p1^2 * p4
# common = p1, cost p2*p3
# then move to p1^2 * p4, cost p1*p4
# total cost p2*p3 + p1*p4
for _ in range(q):
u,v = rl()

pfu = pfs[u]
pfv = pfs[v]
uCost = 0
for p in pfu:
uCost += p * max(0, pfu[p] - pfv.get(p, 0))

vCost = 0
for p in pfv:
vCost += p * max(0, pfv[p] - pfu.get(p, 0))

print(vCost + uCost)``````

## KBG and GN-Theory CodeChef Solution in PYTH

``````import sys
prin = sys.stdout.write
from math import sqrt
from fractions import gcd
MAXN = 100000
spf = [0 for _ in range(MAXN + 1)]  # storing min prime factor
def sieve():
for i in range(1, MAXN + 1):
spf[i] = i
for i in range(2, int(sqrt(MAXN)) + 1):
if spf[i] == i:
for j in range(i*i, MAXN + 1, i):
if spf[j] == j:     # as we want factors in sorted manner
spf[j] = i
def getFactorization(x):
ret = []
ra = ret.append
while x != 1:
ra(spf[x])
x //= spf[x]
return ret
sieve()
for _ in range(int(inpu())) :
n, q = map(int, inpu().split())
# dp = [i for i in range(n + 1)]
# for i in range(2, n + 1) :
#     h = getFactorization(i)
#     for j in h :
#         dp[i] = min(dp[j] + i//j, dp[i])
for _ in range(q) :
a, b = map(int, inpu().split())
gc = gcd(a, b)
ans = sum(getFactorization(a//gc)) + sum(getFactorization(b//gc))
prin(str(ans) + '\n')``````

## KBG and GN-Theory CodeChef Solution in GO

``````package main

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

func main() {

var buf bytes.Buffer
for tc > 0 {
tc--
for q > 0 {
q--
res := solve(u, v)
buf.WriteString(fmt.Sprintf("%d\n", res))
}
}
fmt.Print(buf.String())
}

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
}

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
}

for i := 0; i < len(s); i++ {
if s[i] == '\n' || s[i] == '\r' {
return s[:i]
}
}
return s
}

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
}

const MAX_N = 100010

var F [MAX_N]int

func init() {
for i := 2; i < MAX_N; i++ {
if F[i] == 0 {
for j := i; j < MAX_N; j += i {
if F[j] == 0 {
F[j] = i
}
}
}
}
}

func factorize(num int) map[int]int {
res := make(map[int]int)
for num > 1 {
res[F[num]]++
num /= F[num]
}

return res
}

func solve(u, v int) int64 {
uf := factorize(u)
vf := factorize(v)
var res int64
for f, c1 := range uf {
c2 := vf[f]
res += int64(f) * int64(abs(c1-c2))
}

for f, c2 := range vf {
if _, ok := uf[f]; !ok {
res += int64(f) * int64(c2)
}
}

return res
}

func abs(num int) int {
if num < 0 {
return -num
}
return num
}``````
##### KBG and GN-Theory CodeChef Solution Review:

In our experience, we suggest you solve this KBG and GN-Theory 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 KBG and GN-Theory CodeChef Solution.

Find on CodeChef

##### Conclusion:

I hope this KBG and GN-Theory 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!