Write in Java. Program need to have runtimes < n^2 to satisfy the runtime effici
ID: 3914569 • Letter: W
Question
Write in Java. Program need to have runtimes < n^2 to satisfy the runtime efficiency of some of the testsets.
Question 1: The power is yours
Given three Integer numbers a, b, and N, compute pow(a, b)modN applying divide and conquer methodologies.
Input:
• n specifying the test cases.
• n line where each line with a, b, N three inputs
Output: Each line with the output value of pow(a, b) mod N
Constraints:
1. 1 ? n ? 1000
2. 1 ? a, b, N ? 2^31
Input:
3
3 18132 17
17 1765 3
2374859 3029382 36123
output:
13
2
13195
Explanation / Answer
Source code:
import java.io.*;
import java.util.*;
class Main {
static int power(int x, int y, int p)
{
int res = 1;
x = x % p;
while (y > 0)
{
if((y & 1)==1)
res = (res * x) % p;
y = y >> 1;
x = (x * x) % p;
}
return res;
}
public static void main(String args[])
{
Scanner sc=new Scanner(System.in);
short test_cases=sc.nextShort();
/*while(test_cases>0){
int a= sc.nextInt();
int b=sc.nextInt();
int n=sc.nextInt();
System.out.println(power(a, b, n));
test_cases--;
}*/
int a[] =new int[test_cases];
int b[] =new int[test_cases];
int n[] =new int[test_cases];
for(int i=0;i<test_cases;i++){
a[i]=sc.nextInt();
b[i]=sc.nextInt();
n[i]=sc.nextInt();
}
for(int i=0;i<test_cases;i++){
System.out.println(power(a[i], b[i], n[i]));
}
}
}
Output:
3
3 18132 17
17 1765 3
2374859 3029382 36123
13
2
13195
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.