How do I compute a^b mod C, where b is a large number?
where
a=10
b=6
c= 10^9+7
as i am doing it as pow(a,b)%c then i am getting overflow
How do I compute a^b mod C, where b is a large number?
You can use modular exponentiation (or fast exponentiation also), depending upon value of b, former works in O(b) and latter in O(logb).
in a for loop, keep on multiplying a, taking mod at every iteration.
Fast exponentiation can be done recursively, seed is that a^b = a^(b/2) * a^(b/2) if b is even else a^b = a^(b/2) * a^(b/2) * a , with a base case that b==0 then just return 1.
what about C=10^9+7
means in fast exponential a^b you are calculating then when we should use C
int md = 1e9+7;
int mul(int a,int b){
return (a*b)%md;
}
int power(int a,int n){
if(n==0)
return 1;
int ans = power(a,n/2);
if(n%2)
return mul(mul(ans,ans),a);
return mul(ans,ans);
}
take a look at it
for my code:
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
typedef unsigned long long int ull;
typedef long long int ll;
typedef vector<int> int_vector;
ll gcd(ull a, ull b)
{
if (a == 0)
return (b % MOD);
else
return gcd((b % a) % MOD, b % MOD);
}
ull mul(ull a, ull b)
{
return (a * b) % MOD;
}
ull power(ull a, ull n)
{
if (n == 0)
return 1;
ull ans = power(a, n / 2);
if (n % 2)
return mul(mul(ans, ans), a);
return mul(ans, ans);
}
int main()
{
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
ull arr[100];
ull prod = 1;
for (int i = 0; i < n; i++)
{
cin >> arr[i];
//use ( a * b) % c = ( ( a % c ) * ( b % c ) ) % c
prod = ((arr[i] % MOD) * (prod % MOD)) % MOD;
// prod %= MOD;
}
ull g = arr[0];
for (int i = 1; i < n; i++)
{
g = (gcd(g, arr[i]) % MOD);
}
ull res = power(prod, g);
res = res % MOD;
cout << res << endl;
}
return 0;
}
For Input:
1
9
3585 5404 2652 2755 2400 9933 5061 9677 3369
Your Output is:
893137372
but I am getting 83218077
question is:
Given two function, one is h(x) which includes the products of all the number in an array A[ ]
having size N and another function f(x) which denotes the GCD of all the numbers in an array.
Your task is to find the value of h(x)^f(x).
Note: Since the answer can be very large, use modulo 10^9+7.
Output:
Print the required answer in a new line
Constraints:
1 <= T <= 26
1 <= N <= 60
1 <= Ai <= 104
Example:
Input:
1
2
2 4
Output:
64
Explanation:
Testcase1:Product of the array elements is 8 and GCD of the elements is 2. So 82=64.
Your gcd function is incorrect!
it should be return gcd((b % a), a);
1 Like
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.