posted 1 year ago
Alice and Bob are playing a game on two numbers A and B. Bob has to select a random number X from [1,B].Bob wins the game if gcd(X,B) == gcd(A,B).
Find the probability of Bob wining the game, for given A and B. Let S denotes integer part of probability after multiplying it by pow(10,6).Your task is to find S.
Input format:
The first line contains a long, A, denoting the first given number.
The second line contains a long, B, denoting the second given number.
Constraints:
1 <= A <= 10^12
1 <= B <= 10^12
Input :
4
1
Output:
1000000
Input:
2
10
Output:
4000000
This is what I did, but I kept getting TLE(Time Limit Exceeded) whenever I submit. Please suggest me how I can optimize my solution.