sir i have two number A and B. i have to calculate product form 1 to a and then modulo B.
Constraint
1<=t<=50 for test case
1<=A<=10^9,
1<=B<=10^5,
time limit:1 second
i do it but i am getting tle so please help me and if possible than please give code of it
When a > b, ans is 0 because of pigeonhole principle. When a <= b, calculate by iterating over i from 1 to a, and take ans = (ans * i) % b;
sir but the time limit is 1 second and when a is not greater than than also the answer is zero.pleas see
Sample Input
4-test case
8 10
5 140
18 19
20 21
Sample Output
0
120
18
0
so? this is a linear solution that I have suggested you.
sir what is optimal solution because in linear solution TLE Error is coming
If the constraints that you have written are infact right, this solution should pass the verdict. I don’t understand how it can show TLE. Do you mind sending the link to the problem ?
i have not llink of this problem because this is context problem.i have screenshot of them that i will share with u.
Please share the code also that you have written for the same
#include
using namespace std;
int main() {
int t;
cin>>t;
while(t!=0){
int a,b;
cin>>a>> b;
int ans=1;
for(int i=1;i<=a;i++){
ans=ans*i;
}
ans=ans%b;
cout<<(ans);
t++;
}
}
}
your code is wrong.
int ans = 1;
if(a >= b) ans = 0;
for(int i=1;i<=a;i++) ans = (ans * i) % b;
BRo can you send the full code of java please
import java.util.Scanner;
public class Main {
public static long modularExp(long x, long y, long p) {
long ans = 1;
x = x % p;
while(y > 0) {
if(y % 2 != 0) {
ans = (ans * x) % p;
}
y = y >> 1;
x = (x * x) % p;
}
return ans;
}
public static long inverseMod(long n,long p) {
return modularExp(n, p - 2, p);
}
public static long factorialMod(long n, long p) {
if(n >= p) {
return 0;
}
long ans = (p - 1);
for(long i = n + 1;i < p;i++) {
ans = (ans * inverseMod(i, p)) % p;
}
return ans;
}
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
long t = s.nextLong();
while(t > 0) {
long n = s.nextInt();
long p = s.nextInt();
long ans = factorialMod(n, p);
System.out.println(ans);
t--;
}
}
}
import java.util.Scanner;
public class Main {
public static long modularExp(long x, long y, long p) {
long ans = 1;
x = x % p;
while(y > 0) {
if(y % 2 != 0) {
ans = (ans * x) % p;
}
y = y >> 1;
x = (x * x) % p;
}
return ans;
}
public static long inverseMod(long n,long p) {
return modularExp(n, p - 2, p);
}
public static long factorialMod(long n, long p) {
if(n >= p) {
return 0;
}
long ans = (p - 1);
for(long i = n + 1;i < p;i++) {
ans = (ans * inverseMod(i, p)) % p;
}
return ans;
}
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
long t = s.nextLong();
while(t > 0) {
long n = s.nextInt();
long p = s.nextInt();
long ans = factorialMod(n, p);
System.out.println(ans);
t--;
}
}
}