# QLK05 - EDITORIAL

Practice

Contest

Author: Pritish Priyatosh Nayak

Tester: Saytabrat Panda

Editorialist: Pritish Priyatosh Nayak

Cakewalk

None

# PROBLEM:

The problem is basically :
Given N and K, check if N^N \geq K.

# QUICK EXPLANATION:

To avoid overflow while calculating we can print “Yes” for all cases where N \geq 16 otherwise calculate N^N manually and check the condition.

# EXPLANATION:

From the constraints its clear that we need either O(1) solution or O(logN) solution.

But we cannot calculate N^N for any N \geq 16 because 16^{16} turns out to be 2^{64} and even the maximum positive number which can be stored in unsigned long long data type of C/C++ is 2^64-1.
If we actually try to calculate N^N we will run into overflow error.
Even with languages like Python it’s still not possible to calculate N^N for such large N because it will be very slow.

But K is at max 10^{18} which is less than 16^{16} , so we need to only check for N less than 16 manually and compare it with K.
If N is greater than or equal to 16, the answer is obviously “Yes”.

Alternate approach:
You could have used the fact that if N^N \geq K then Nlog(N) \geq log(K).
Using the inbuilt log functions , it could have been solved easily without having to use any short-cut tricks.

# SOLUTIONS:

Setter's/Editorialist's Solution
``````#include<bits/stdc++.h>
using namespace std;
long long pow(long long x,long long y)
{
long long res=1;
for(long long i=1;i<=y;i++)
res*=x;
return res;
}
int main()
{
int t;
cin>>t;
while(t--)
{
long long n,k;
cin>>n>>k;
if(n>=16)
cout<<"Yes\n";
else if(pow(n,n)>=k)
cout<<"Yes\n";
else cout<<"No\n";
}
return 0;
}
``````
Tester's Solution
``````import java.util.*;import java.io.*;import java.math.*;

public class Main
{

public static void process()throws IOException
{
long n=nl(),k=nl();

assert (n>1e18 || k>1e18):"N or K > 1e18";
pn((n*Math.log(n)>=Math.log(k))?"Yes":"No");
}

static PrintWriter out;
public static void main(String[]args)throws IOException
{
out = new PrintWriter(System.out);
boolean oj = true;

//oj = System.getProperty("ONLINE_JUDGE") != null;

long s = System.currentTimeMillis();
int t=1;
t=ni();
while(t-->0)
process();
out.flush();
if(!oj)
System.out.println(System.currentTimeMillis()-s+"ms");
System.out.close();
}

static void pn(Object o){out.println(o);}
static void p(Object o){out.print(o);}
static void pni(Object o){out.println(o);System.out.flush();}
static int ni()throws IOException{return sc.nextInt();}
static long nl()throws IOException{return sc.nextLong();}
static double nd()throws IOException{return sc.nextDouble();}
static String nln()throws IOException{return sc.nextLine();}
static long gcd(long a, long b)throws IOException{return (b==0)?a:gcd(b,a%b);}
static int gcd(int a, int b)throws IOException{return (b==0)?a:gcd(b,a%b);}
static int bit(long n)throws IOException{return (n==0)?0:(1+bit(n&(n-1)));}
static boolean multipleTC=false;
static long mod=(long)1e9+7l;

static void r_sort(int arr[],int n){
Random r = new Random();
for (int i = n-1; i > 0; i--){
int j = r.nextInt(i+1);

int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
Arrays.sort(arr);
}

static long mpow(long x, long n) {
if(n == 0)
return 1;
if(n % 2 == 0) {
long root = mpow(x, n / 2);
return root * root % mod;
}else {
return x * mpow(x, n - 1) % mod;
}
}

static long mcomb(long a, long b) {
if(b > a - b)
return mcomb(a, a - b);
long m = 1;
long d = 1;
long i;
for(i = 0; i < b; i++) {
m *= (a - i);
m %= mod;
d *= (i + 1);
d %= mod;
}
long ans = m * mpow(d, mod - 2) % mod;
return ans;
}
/////////////////////////////////////////////////////////////////////////////////////////////////////////

String next()throws IOException{
while (st == null || !st.hasMoreElements()) {try{
catch (IOException  e){ e.printStackTrace(); }}
return st.nextToken(); } int nextInt() throws IOException{
return Integer.parseInt(next());}
long nextLong() throws IOException
{return Long.parseLong(next());}
double nextDouble()throws IOException { return Double.parseDouble(next()); }
String nextLine() throws IOException{ String str = ""; try{
str = br.readLine();} catch (IOException e){
e.printStackTrace();} return str;}}
/////////////////////////////////////////////////////////////////////////////////////////////////////////////
}

``````
2 Likes

nice question bro,but as usual i m damn stupid