HackerRank Algebra – Simple One

Challenge: Simple One

Subdomeniu: Algebra (algebra)

Scor cont: 30.0 / 30

Submission status: Accepted

Submission score: 1.0

Submission ID: 464727326

Limbaj: python3

Link challenge: https://www.hackerrank.com/challenges/simple-one/problem

Cerinta

You are given the equation $\tan\alpha = \frac{p}{q}$ and a positive integer, $n$. Calculate $\tan n\alpha$. There are $T$ test cases.

Input Format

The first line contains $T$, the number of test cases.   
The next $T$ lines contain three space separated integers: $p, q$ and $n$, respectively.  

**Constraints**  
$0 \leqslant p \leqslant 10^9$  
$1 \leqslant q \leqslant 10^9$  
$1 \leqslant n \leqslant 10^9$  
$T \leqslant 10^4$

Output Format

If the result is defined, it is always a rational number. However, it can be very big.  
Output the answer modulo $(10^9 + 7)$.  
If the answer is $\frac{a}{b}$ and $b$ is not divisible by $(10^9+7)$, there is a unique integer $0 \leqslant x < 10^9 + 7$ where $a \equiv bx \mod (10^9 + 7)$.  
Output this integer, $x$.  
It is guaranteed that $b$ is not divisible by $(10^9 + 7)$ for all test cases.

Cod sursa

M = 1000000007


def power(x, y):
    x %= M
    ans = 1
    while y > 0:
        if y & 1 == 1:
            ans = ans*x % M
        x = x*x % M
        y >>= 1
    return(ans)


def tan(b, n):
    if n == 1:
        return b
    if n % 2 == 0:
        a = tan(b, n//2)
        return(2*a % M*power((1-a**2 % M+M) % M, M-2) % M)
    else:
        a = tan(b, n-1)
        soorat = (a+b) % M
        makhraj = (1-a*b % M+M) % M
        return(soorat*power(makhraj, M-2) % M)


def solve(p, q, n):
    return(tan(p*power(q, M-2) % M, n))


for _ in range(int(input())):
    p, q, n = map(int, input().split())
    print(solve(p, q, n))