Distinct Numbers CodeChef Solution

Problem -Distinct Numbers 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.

Distinct Numbers CodeChef Solution in C++17

“ ”

#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;

template <class T>
using OS =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define ll long long
#define ld double
#define ull unsigned long long

ll mod = 1e9 + 7;

ll fp(ll a, ll b, ll m) {
  a %= m;
  ll res = 1, mult = a;
  while (b) {
    if (b & 1) res = res * mult % m;
    mult = mult * mult % m;
    b >>= 1;
  }
  return res;
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  int t;
  cin >> t;
  while (t--) {
    ll n, k;
    cin >> n >> k;

    map<ll, ll> pp;
    while (n % 2 == 0) n /= 2, pp[2]++;
    for (ll i = 3; i * i <= n; i += 2) {
      while (n % i == 0) pp[i]++, n /= i;
    }
    if (n > 1) pp[n]++;

    map<ll, ll> ss;
    for (auto &p : pp) {
      ll pw = (fp(2, k, mod - 1) * p.second + 1) % (mod - 1);
      ll num = (fp(p.first, pw, mod) - fp(p.first, p.second, mod) + mod) % mod;
      ll den = fp(p.first - 1, mod - 2, mod);
      ss[p.first] = (num * den) % mod;
    }

    ll ans = 1;
    for (auto &i : ss) {
      ans = ans * i.second % mod;
    }
    cout << ans;

    cout << '\n';
  }

  return 0;
}

Distinct Numbers CodeChef Solution in C++14

“ ”

#include <bits/stdc++.h>
//for policy based ds //p.order_of_key() -> returns index of value //*p.find_by_order(3) ->value at index
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp>
#include <functional> // for less

using namespace __gnu_pbds; //for policy based ds
using namespace std;

#define int long long
#define pii pair<int, int>
#define vi vector<int>
#define maxHeap priority_queue<int>;
#define minHeap priority_queue<int, vi, greater<int>>
#define mod 1000000007
#define inf 1e18
#define rep(i, s, n) for (int i = s; i < n; i++)
#define sp(ans, pre) fixed << setprecision(pre) << y
#define pb push_back
#define srt(v) sort(v.begin(), v.end())
#define all(v) begin(v), end(v)
#define inputArr(i, arr) \
    for (int &i : arr)   \
        cin >> i;
#define ll long long
#define ull unsigned long long
#define lld long double
#define kickPrint(tt) cout << "Case #" << tt << ": "

typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> pbds;

time_t Begin;

//////////////////Debug///////////////
#define debug(x)       \
    cout << #x << " "; \
    _print(x);         \
    cout << endl;
void _print(ll t)
{
    cout << t;
}
//void _print(int t) {cout << t;}
void _print(string t) { cout << t; }
void _print(char t) { cout << t; }
void _print(lld t) { cout << t; }
void _print(double t) { cout << t; }
void _print(ull t) { cout << t; }
void display(ll a[], ll n)
{
    for (ll i = 0; i < n; i++)
    {
        cout << a[i] << " ";
    }
    cout << endl;
}

template <class T, class V>
void _print(pair<T, V> p);
template <class T>
void _print(vector<T> v);
template <class T>
void _print(set<T> v);
template <class T, class V>
void _print(map<T, V> v);
template <class T>
void _print(multiset<T> v);
template <class T, class V>
void _print(pair<T, V> p)
{
    cout << "{";
    _print(p.ff);
    cout << ",";
    _print(p.ss);
    cout << "}";
}
template <class T>
void _print(vector<T> v)
{
    cout << "[ ";
    for (T i : v)
    {
        _print(i);
        cout << " ";
    }
    cout << "]";
}
template <class T>
void _print(set<T> v)
{
    cout << "[ ";
    for (T i : v)
    {
        _print(i);
        cout << " ";
    }
    cout << "]";
}
template <class T>
void _print(multiset<T> v)
{
    cout << "[ ";
    for (T i : v)
    {
        _print(i);
        cout << " ";
    }
    cout << "]";
}
template <class T, class V>
void _print(map<T, V> v)
{
    cout << "[ ";
    for (auto i : v)
    {
        _print(i);
        cout << " ";
    }
    cout << "]";
}
template <typename T, typename U>
inline bool chmax(T &a, U b) { return a < b ? (a = b, true) : false; }
template <typename T, typename U>
inline bool chmin(T &a, U b) { return a > b ? (a = b, true) : false; }

void init()
{
    Begin = clock();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}
void timeTaken()
{
#ifndef ONLINE_JUDGE
    double time_taken = double(clock() - Begin) / double(CLOCKS_PER_SEC);
    cout << "Execution Time: " << fixed << setprecision(5) << time_taken << "s\n";
#endif
}

vector<int> computeLps(string s, int M)
{
    int len = 0;
    vector<int> lps(M + 20);

    lps[0] = 0;

    int i = 1;
    while (i < M)
    {
        if (s[i] == s[len])
        {
            len++;
            lps[i] = len;
            i++;
        }
        else
        {
            if (len != 0)
            {
                len = lps[len - 1];
            }
            else
            {
                lps[i] = 0;
                i++;
            }
        }
    }
    // debug(len);
    return lps;
}

int ceiling(int x, int y)
{
    int res = x / y;
    if (x % y)
    {
        if (x >= 0)
            res++;
    }
    return res;
}

vector<vector<int>> makePrefix(vector<vector<int>> &grid)
{
    int n = grid.size(), m = grid[0].size();
    vector<vector<int>> prefix(n + 1, vector<int>(m + 1));

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            prefix[i + 1][j + 1] = grid[i][j] + prefix[i][j + 1] + prefix[i + 1][j] - prefix[i][j];
        }
    }

    return prefix;
}

int query(int x1, int y1, int x2, int y2, vector<vector<int>> &prefix)
{
    // cout << x1 << " " << y1 << " " << x2 << " " << y2 << endl;

    // cout << "query: " << prefix[x2 + 1][y2 + 1] << " " << prefix[x2 + 1][y1] << " " << prefix[x1][y2 + 1] << " " << prefix[x1][y2] << endl;
    return prefix[x2 + 1][y2 + 1] - prefix[x2 + 1][y1] - prefix[x1][y2 + 1] + prefix[x1][y1];
}

int toInt(string &s)
{
    int res = 0;
    for (char c : s)
        res = res * 10 + (c - '0');
    return res;
}

bool isValid(int i, int j, int n, int m)
{
    return i >= 0 && i < n && j >= 0 && j < m;
}

int dx[] = {-1, 0, 0, 1};
int dy[] = {0, 1, -1, 0};

int moduloExponentiation(int a, int b, int m)
{
    if (b == 0)
        return 1;

    int res = moduloExponentiation(a, b / 2, m);
    res = (res * res) % m;

    if (b % 2)
        res = (res * a) % m;
    return res;
}

int gp(int p, int e, int k)
{
    int modexp = moduloExponentiation(2, k, mod - 1);
    modexp = ((((e % (mod - 1)) * (modexp % (mod - 1))) % (mod - 1)) + 1) % (mod - 1);
    int numi = (moduloExponentiation(p, modexp, mod) - 1 + mod) % mod;
    int deno = moduloExponentiation(p - 1, mod - 2, mod);
    // cout << numi << " -- " << deno << " " << modexp << endl;
    return (numi * deno) % mod;
}

int sumOfDivisors(int n, int k)
{
    int res = 1;
    for (int i = 2; i * i <= n; i++)
    {
        int cnt = 0;
        int pow = 1;
        while (n % i == 0)
        {
            n /= i;
            cnt++;
        }

        if (cnt)
        {
            int sum = (gp(i, cnt, k) - gp(i, cnt - 1, 0) + mod) % mod;
            // cout << i << ":" << cnt << ":" << sum << "#"; // << gp(i, cnt, k) << ":" << gp(i, cnt, 0) << " ";
            res = (res * sum) % mod;
        }
    }

    if (n > 1)
    {
        int cnt = 1;
        int sum = (gp(n, cnt, k) - gp(n, cnt - 1, 0) + mod) % mod;
        // cout << i << ":" << cnt << ":" << sum << "#"; // << gp(i, cnt, k) << ":" << gp(i, cnt, 0) << " ";
        res = (res * sum) % mod;
    }
    // cout << "-----------------\n";
    return res;
}
int32_t main()
{
    init();
    //--------------------
    int t = 1;
    cin >> t;
    for (int tt = 1; tt <= t; tt++)
    {
        int n, k;
        cin >> n >> k;
        cout << sumOfDivisors(n, k) << "\n";
    }
    //---------------------------
    timeTaken();
    return 0;
}

Distinct Numbers CodeChef Solution in PYTH 3

“ ”

cons = 1000000007
T = int(input())
for i in range(T):
    def p1(y, z, cons):
        ans = 1
        while z:
            if z % 2 == 1:
                ans = ans * y % cons
            y = y * y % cons
            z //= 2
        return ans

    def p2(x, y):
        if y >= 30:
            return p1(x, p1(2, y, cons - 1) + cons - 1, cons)
        return p1(x, (1<<y), cons)
        return int(' ')

    def calc(a, x, b):
        return (p1(p2(a, b), x, cons) - p1(a, x - 1, cons) + cons) % cons * a % cons * p1(a - 1, cons - 2, cons) % cons

    a, b  = map(int, input().split())
    Sum = 1
    
    for j in range(2, a):
        if j * j > a:
            break
        c = 0
        while a % j == 0:
            c += 1
            a //= j
        if c != 0:
            Sum = Sum * calc(j, c, b) % cons
    if a != 1:
        Sum=Sum * calc(a, 1, b) % 1000000007
    print(Sum)

Distinct Numbers CodeChef Solution in JAVA

“ ”

import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.PrintStream;
import java.util.HashMap;
import java.util.Random;
import java.util.ArrayList;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastReader in = new FastReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        DistinctNumbers solver = new DistinctNumbers();
        int testCount = Integer.parseInt(in.next());
        for (int i = 1; i <= testCount; i++)
            solver.solve(i, in, out);
        out.close();
    }

    static class DistinctNumbers {
        final static Helper hp = new Helper();
        final long MOD = hp.MOD;
        int N;
        int K;

        public void fillInputParams(FastReader in) {
            N = in.nextInt();
            K = in.nextInt();
        }

        Object solveOptimised(FastReader in, StringBuilder sb) {
            ArrayList<Integer> factors = hp.primeFactorise(N);
            HashMap<Long, Integer> map = new HashMap<>();
            for (long itr : factors) {
                map.put(itr, map.getOrDefault(itr, 0) + 1);
            }

            // N * (gpsum(a = 1, r = p, n = 2^k + 1) for all p)
            long ret = N, den = 1;
            for (long prime : map.keySet()) {
                long maxReach = map.get(prime) * hp.pow(2, K, MOD - 1) % (MOD - 1);
                long terms = (maxReach - map.get(prime) + 1) % (MOD - 1);
                long gpSum = hp.pow(prime, terms, MOD) - 1;
                den = den * (prime - 1) % MOD;
                ret = ret * gpSum % MOD;
            }

            return ret * hp.getInvModulo(den) % MOD;
        }

        Object solveBrute(FastReader in, StringBuilder sb) {
            return null;
        }

        public void solve(int testNumber, FastReader in, PrintWriter out) {
            // out.print("Case #" + testNumber + ": ");

            fillInputParams(in);
            Object outOptimised = solveOptimised(in, new StringBuilder());
            Object outBrute = solveBrute(in, new StringBuilder());
            if (outBrute == null) {
                out.println(outOptimised);
            } else if (outBrute.toString().equals(outOptimised.toString())) {
                System.err.println(testNumber + ". OK Checked");
            } else {
                // print input params
                System.err.println("Actual = " + outOptimised);
                System.err.println("Expected = " + outBrute);
                System.err.println();
                throw new ArithmeticException();
            }
        }

    }

    static class FastReader {
        static final int BUFSIZE = 1 << 20;
        static byte[] buf;
        static int index;
        static int total;
        static InputStream in;

        public FastReader(InputStream is) {
            try {
                in = is;
                buf = new byte[BUFSIZE];
            } catch (Exception e) {
            }
        }

        private int scan() {
            try {
                if (index >= total) {
                    index = 0;
                    total = in.read(buf);
                    if (total <= 0)
                        return -1;
                }
                return buf[index++];
            } catch (Exception | Error e) {
                System.err.println(e.getMessage());
                return 13 / 0;
            }
        }

        public String next() {
            int c;
            for (c = scan(); c <= 32; c = scan()) ;
            StringBuilder sb = new StringBuilder();
            for (; c > 32; c = scan())
                sb.append((char) c);
            return sb.toString();
        }

        public int nextInt() {
            int c, val = 0;
            for (c = scan(); c <= 32; c = scan()) ;
            boolean neg = c == '-';
            if (c == '-' || c == '+')
                c = scan();
            for (; c >= '0' && c <= '9'; c = scan())
                val = (val << 3) + (val << 1) + (c & 15);
            return neg ? -val : val;
        }

    }

    static class Helper {
        public final long MOD;
        public final int MAXN;
        final Random rnd;
        public static int[] sieve;
        public static ArrayList<Integer> primes;
        public static long[] invNaturalNum;

        public Helper() {
            MOD = 1000_000_007;
            MAXN = 1000_006;
            rnd = new Random();
        }

        public Helper(long mod, int maxn) {
            MOD = mod;
            MAXN = maxn;
            rnd = new Random();
        }

        public void setSieve() {
            if (sieve == null || sieve.length < MAXN) {
                primes = new ArrayList<>();
                sieve = new int[MAXN];
                int i, j;
                for (i = 2; i < MAXN; ++i) {
                    if (sieve[i] == 0) {
                        primes.add(i);
                        for (j = i; j < MAXN; j += i) {
                            if (sieve[j] == 0) sieve[j] = i;
                        }
                    }
                }
            }
        }

        public ArrayList<Integer> primeFactorise(int num) {
            setSieve();
            ArrayList<Integer> factors = new ArrayList<>();
            for (int prime : primes) {
                if (prime * prime <= num) {
                    while (num % prime == 0) {
                        factors.add(prime);
                        num /= prime;
                    }
                } else {
                    break;
                }
            }
            if (num > 1) factors.add(num);
            return factors;
        }

        public void setInvNaturalNum() {
            invNaturalNum = new long[MAXN];
            invNaturalNum[0] = invNaturalNum[1] = 1;
            for (int i = 2; i < MAXN; ++i) {
                invNaturalNum[i] = invNaturalNum[(int) (MOD % i)] * (MOD - MOD / i) % MOD;
            }
        }

        public long getInvModulo(long n) { // MOD must be prime
            if (n >= MAXN) return pow(n, MOD - 2, MOD);
            else if (invNaturalNum == null) setInvNaturalNum();
            return invNaturalNum[(int) n];
        }

        public long pow(long base, long exp, long MOD) {
            base %= MOD;
            long ret = 1;
            while (exp > 0) {
                if ((exp & 1) == 1) ret = ret * base % MOD;
                base = base * base % MOD;
                exp >>= 1;
            }
            return ret;
        }

    }
}

Distinct Numbers CodeChef Solution in PYPY 3

“ ”

MOD = 10**9 + 7


def solve(p, a, k):
    first = pow(p, a, MOD)
    terms = (pow(2, k, MOD - 1) * a - a + 1) % (MOD - 1)
    res = first * (pow(p, terms, MOD) - 1) % MOD
    res = (res * pow(p - 1, MOD - 2, MOD)) % MOD
    return res


for _ in range(int(input())):
    ans = 1
    N, K = map(int, input().split())
    for i in range(2, N + 1):
        if i * i > N:   
            break
        if N % i != 0:
            continue
        cnt = 0
        while N % i == 0:
            N //= i
            cnt += 1
        ans = (ans * solve(i, cnt, K)) % MOD
    if N > 1:
        ans = (ans * solve(N, 1, K)) % MOD
    print(ans)

Distinct Numbers CodeChef Solution in PYTH

“ ”

D = 1000000007

def power(x, n, M):
	p = 1
	while n > 0:
		if n % 2 == 1:
			p = p * x % M
		x = x * x % M
		n >>= 1
	return p

def Apower(a, b):
	if b >= 30:
		return power(a, power(2, b, D - 1) + D - 1, D)
	return power(a, (1 << b), D)

def calc(n, p, k):
	return (power(Apower(n, k), p, D) - power(n, p - 1, D) + D) % D * n % D * power(n - 1, D - 2, D) % D

class myc:
	def __init__(self, a):
		self.n = a[0]
		self.k = a[1]

	def solve(self):
		rez = 1
		e = 0
		while self.n % 2 == 0:
			e += 1
			self.n >>= 1
		if e > 0:
			rez = rez * calc(2, e, self.k) % D
		d = 3	
		while d * d <= self.n:
			if self.n % d == 0:
				e = 0
				while self.n % d == 0:
					e += 1
					self.n /= d
				rez = rez * calc(d, e, self.k) % D
			d += 2
		if self.n > 1:
			rez = rez * calc(self.n, 1, self.k) % D
		return rez

def main():
	t = int(raw_input())
	while t > 0:
		t -= 1
		a = [int(x) for x in raw_input().split()]
		ob = myc(a)
		print ob.solve()

if __name__ == '__main__':
	main()

Distinct Numbers CodeChef Solution in GO

“ ”

package main

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

func main() {
	reader := bufio.NewReader(os.Stdin)

	var buf bytes.Buffer

	tc := readNum(reader)

	for tc > 0 {
		tc--
		n, k := readTwoNums(reader)
		res := solve(n, k)
		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
}
func solve(n int, k int) int {
	// 假设 n 的 质因数是, a, b, c
	// 就是 n * a ** cnt(a) * b ** cnt(b) * c * cnt(c)
	// cnt(a) + cnt(b) + cnt(c) <= k
	ans := 1
	for i := 2; i <= n/i; i++ {
		if n%i > 0 {
			continue
		}
		var cnt int
		for n%i == 0 {
			n /= i
			cnt++
		}
		ans = modMul(ans, sum_of_prime_factors(i, cnt, k), MOD)
	}

	if n > 1 {
		ans = modMul(ans, sum_of_prime_factors(n, 1, k), MOD)
	}

	return ans
}

func sum_of_prime_factors(p int, a int, k int) int {
	first := int64(pow(p, a, MOD))
	ratio := int64(p)
	terms := (int64(pow(2, k, MOD-1))*int64(a) - int64(a) + 1) % int64(MOD-1)
	res := (first * int64(pow(int(ratio), int(terms), MOD)-1)) % MOD
	res *= int64(pow(int(ratio-1), MOD-2, MOD))
	return int(res % MOD)
}

const MOD = 1000000007

func modAdd(a, b int) int {
	a += b
	if a >= MOD {
		a -= MOD
	}
	return a
}

func modMul(a, b int, mod int) int {
	r := int64(a) * int64(b)
	return int(r % int64(mod))
}

func pow(a, b, mod int) int {
	r := 1
	for b > 0 {
		if b&1 == 1 {
			r = modMul(r, a, mod)
		}
		a = modMul(a, a, mod)
		b >>= 1
	}
	return r
}

Distinct Numbers CodeChef Solution Review:

In our experience, we suggest you solve this Distinct Numbers 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 Distinct Numbers CodeChef Solution.

Find on CodeChef

“ ”

Conclusion:

I hope this Distinct Numbers 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