Question

given pair (a,b) after each unit of time pair (a,b) get changed to (b-a,b+a).you are given the initial value of pair and an integer n and you to print the value of pair at the nth unit of time.

input format:

1.First line:t donating the number of test cases

2.Next t lines:three space-seperated integer a,b and n

output format :

for each test case ,print two integers (mod 10^9 +7) per

line denoting the value of the pair at the n th unit time.

constrains:

1<t< 10^6

0< a<b<10^9

1<n<10^5

sample input :

5

1 3 5

2 3 9  

sample output

4 12

32 48

81920 131072

Answer 1

In 1 seconds we can make 10^8 operations to run in a CPU and the judges of online programming contests.

If you use a imple approach to to loop for n times ,the solution will time out because the it would take t*n =10^6*10^5

=10^11 operatiosn per scond which we give a Time Limit Exceeded error.So we nee dto reduce our complexity

.We cannot reduce the contrinution of t but we can reduce for the contrinution of n in complexity.We can observe the following :

The time T	The value of a	The value of b
t=1	a(original)	b(original)
t=2	b-a	b+a
t=3	(b+a)-(b-a)=2a	(b+a)+(b-a)=2b
t=4	2b-2a=2(b-a)	2b+2a=2(b+a)
t=5	2(b+a)-2(b-a)=4a	2(b+a)+2(b-a)=4b
t=6	4(b-a)	4(b+a)
t=7	8a	8b
and so on...

We can take the inference from above that At odd values of t ,The value

a= (2^((t-1)/2))*a and b=(2^((t-1)/2))*b;

and At even values of t ,The value of t,a=(2^(t/2-1))*(b-a) and ,b=(2^(t/2-1))*(b+a)

which can be calculated in O(1) time.

Also we have used a modulo function to find (a^b)%mod with complexity log(b).

So the overalll complexity of the  questions is t*O(logn).

The question is running on standard test cases,I hope it will definitely run on all,if it does not plz provide more test case I am there to help

Feel free to comment if any doubts

import java.util.Scanner;

public class Swapper {
  static int mod=(int)10e9+7;



    public static long pow(long a,long b)
  {
      if(b==0)
          return 1;
      long temp=pow(a,b/2);
      long f=(temp*temp)%mod;
      if(b%2==0)
          return f;
      else
          return (a*f)%mod;

  }
    public static void main(String args[])
    {
        Scanner s=new Scanner(System.in);
        int x=s.nextInt();
        while(x--!=0) {
            long a = s.nextLong();
             long b=s.nextLong();
             int t=s.nextInt();
             if(t%2!=0)
            {
               a=(a*pow(2,(t-1)/2))%mod ;
               b=(b*pow(2,(t-1)/2))%mod ;

            }
             else
             {
                 long temp=a;
                 a=((b-a)*pow(2,t/2-1))%mod ;
                 b=((b+temp)%mod*pow(2,t/2-1)%mod )%mod;

             }
             System.out.println(a%mod+" "+b%mod);


        }
    }
}