304 North Cardinal St.
Dorchester Center, MA 02124

# Distinct Numbers CodeChef Solution

## 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;
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;

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 final int BUFSIZE = 1 << 20;
static byte[] buf;
static int index;
static int total;
static InputStream in;

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

private int scan() {
try {
if (index >= total) {
index = 0;
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) {
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) {
num /= prime;
}
} else {
break;
}
}
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() {

var buf bytes.Buffer

for tc > 0 {
tc--
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
}

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
}
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!