Arun has an integer N. His friend Sucksum likes the number 1, so Arun wants to reduce N to 1.
To do so, he can perform the following move several times (possibly, zero):
Pick two integers X and Y such that X+Y is even and X^Y is a divisor of N. Then, replace N by \dfrac{N}{X^Y}
Note that at each step, X^Y only needs to be a divisor of the current value of N, and not necessarily a divisor of the integer Arun initially started with.
Find the minimum number of moves Arun needs to reduce N to 1. If it is not possible to reduce N to 1 using the given operation, print -1 instead.
EXPLANATION:
Let us tackle this problem case-wise for N, but before that we define another variable count which stores the count of power of 2 for N.
N = 1: Answer would be 0, since we already are at 1.
count = 0. Answer would be 1 since then N would be odd so we can take X = N and Y = 1. Then X+Y would be even and X^Y would be N, that is a divisor of N which would reduce it to 1.
count \;is\; odd: We cannot reach 1. Taking 2 here, we would observe that it cannot be reduced to 1. Similarly for any other number, we would at best reduce it to 2 and then get stuck.
N\;is\;a\;perfect\;square: Here we take X = \sqrt{N} and Y=2. Since X would also have a power of 2 so it would be even, thus X+Y would be even and X^Y would be N, that is a divisor of N which would reduce it to 1 so answer would be 1
Otherwise: We are talking about cases where N is not a perfect square and count is even. Here we would first take X = 2^{count/2} and Y=2. This would reduce N to N' that does not contain any power of 2. This would then be the same case as above so we would require one more move. Overall answer would be 2.
4^2 = 16 and lets say you try to convert 2^X into (2^Y)^Z and you claim 2^Y + Z is even. We know 2^Y will be even so Z also needs to be even but Y*Z = X and as X is odd both Y and Z are necessarily odd, hence your claim is rejected.
I observed something in this question
If I use binary search to find square root of number , then I get WA , but when I use inbuilt sqrt to solve this problem I get AC ,
can anyone please tell the mistake in my code with relevant examples
#include #include
using namespace std;
int main(){
long long int t;
cin>>t;
for(long long int i=0;i<t;i++){
long long int n,c=0;
cin>>n;
if(n==1){
cout<<0<<endl;
}
else if(n%2!=0){
cout<<1<<endl;
}
else{
while(n%2==0){
n=n/2;
c++;
}
if(c%2==0){
if(n==1){
cout<<1<<endl;
}
else{
cout<<2<<endl;
}
}
else{
cout<<-1<<endl;
}
}
}
return 0;
}
