Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
KBG and GN-Theory CodeChef Solution
Problem -KBG and GN-Theory 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.
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 read() {
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() {
T=read();
while(T--) {
n=read();
q=read();
while(q--) {
int x=read(),y=read();
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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.concurrent.ThreadLocalRandom;
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 {
BufferedReader br;
StringTokenizer st;
public FastScanner() {
br = new BufferedReader(new InputStreamReader(System.in));
}
String nextToken() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
return st.nextToken();
}
String nextLine() {
try {
return br.readLine();
} 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 class ADUtils {
static void sort(int[] ar) {
Random rnd = ThreadLocalRandom.current();
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) {
Random rnd = ThreadLocalRandom.current();
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
input = stdin.readline
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
inpu = sys.stdin.readline
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() {
reader := bufio.NewReader(os.Stdin)
tc := readNum(reader)
var buf bytes.Buffer
for tc > 0 {
tc--
_, q := readTwoNums(reader)
for q > 0 {
q--
u, v := readTwoNums(reader)
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
}
func readString(reader *bufio.Reader) string {
s, _ := reader.ReadString('\n')
for i := 0; i < len(s); i++ {
if s[i] == '\n' || s[i] == '\r' {
return s[:i]
}
}
return s
}
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
}
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.
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!
