Factorial of large number

[STD8C542]

i want to get factorial of a number as large number as 10^6 with modulo 10^9+7.
i also have the test case with t upto 10^5 and factorial of a number n upto 10^6 with a time limit of 1s.
This brute force isn't helping me

  #include <bits/stdc++.h>
using namespace std;

long int mod = 1000000007;
long int fac(long int i){
    long int ans = 1;
    for(long int j = i; j > 1; j--)
        ans = (ans*j)%mod; //factorial
    return ans;
}

int main() {
	ios_base::sync_with_stdio(false);
        cin.tie(NULL);
	int t; //test case
	long int n;
	cin >> t;
	while(t--){
	    cin >> n;
	    long int a = (fac(n)) % mod;
	    cout << a << endl;
	}
}

[Duthomhas]

You need a bignum library. I suggest Boost MultiPrecision. The (default) cpp backend should suffice.

[Ganado]

I've never done this, but I believe the trick here is to avoid BigNum-type libraries by always keeping the computation within (or just above) 10^9 + 7.

https://www.geeksforgeeks.org/modulo-1097-1000000007/

iotaa, are you saying that your math is correct, but just too slow? If so, I think you need an algorithm that takes advantage of the special properties when mod'ing something by a prime number.

I'm still thinking about it, but I think the efficient answer might involve modular exponentiation.
https://en.wikipedia.org/wiki/Modular_exponentiation#Right-to-left_binary_method

Maybe https://en.wikipedia.org/wiki/Modular_multiplicative_inverse

Sorry, I don't actually know the exact way to solve it. But I can almost guarantee there's a more efficient way than your method. You could google it and cheat... but what's the fun in that?

[STD8C542]

@Ganado yes this approach is too slow and giving me tle for large number of t and n

[jonnin]

do you need it exact?
there are a couple of approximations out there.

[Duthomhas]

A bignum library will have routines optimized to do stuff modulo some number.