A^b = a+b , given a find the smallest b possible

general
,
1

Alice wants to send a secret message to Bob. She encrypts the message with the public key (pub) of Bob and sends the message. Eve tries to perform an attack on the message. She knows that the public key and private key are related to each other with the following boolean relation:

pub ^ prv = pub + prv

Now as Eve knows the public key of Bob, she wants to determine his private key using the above relation.

Note: Bob has n private keys.

Input Format

  • The first line contains a single integer q, the number of queries.
  • Each of the next q lines contain a integer, the public keys of Bob.

Constraints

  • 1 <= q <= 15
  • 1 <= pub, prv < 10^18

Output Format

For each query, print smallest private key of Bob on a new line.

Sample Input 0

2 4 19

Sample Output 0

1 4

Explanation 0

for first input, pub = 4:

4^1 = 5 = 4+1, 4^3 = 7 = 4+3, 4^9 = 13 = 4+9 and so on..

But out of 1, 3, 9, . . . the smallest one is 1.

The below is my code, which just finds the first occurrence of 0 of the number , but it is not able to pass all the test cases, I know there is some minor mistake, but I am unable to point it out, any help or any other solution will be great. thank you

#include
#include
#include
#include
#include
using namespace std;

int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
int q;
cin>>q;
while(q–){
long long int pub;
cin>>pub;

    for(long long int i=0;i<=64;i++){
        
        if((pub & (long long int)(1<<i)) == 0){
            
            cout<<pow(2,i)<<endl;
            break;
        }
    }
}
return 0;

}

2

It should be (1ll<<i), you need to cast the 1 to long long.

2 Likes
3

thank you for the reply, but it’s still not working, 2 test cases are still failing, as it was previously.

4

Do you have a link to the problem?

5

tell me if its working or not.

6

pow returns something like 9e+ 42 for huge numbers which gives WA.
Why not use 1LL << i again?
alternatively, you could use cout << setprecision(0) << fixed << pow(2, i)

2 Likes
7

You cud also first store it in a variable like ans = pow(2, i); then output ans

1 Like
8

Yes, the link is working. As said by @singlabharat , you can use (1LL << i) again since pow() function works with doubles and shows unexpected behaviour.

1 Like
9

thank you @singlabharat @suman_18733097 . I was actually not aware of that , now its working just fine. Big Thanx!!

10

Yeah np