Math day hint for comptetive coding q

#1

Math Day is being celebrated at Coding Blocks. So Prateek Bhaiya rolled out a contest on Maths Problems. Here goes one.
Given three positive integers A,N,P. Compute AN! %P.
how to solve this q?

#2

hello @sunneykumar309

use modular exponentiation to calcuate A^ N! %p

i.e
A^N! % P =((( (A^N % p ) ^ N-1)%p)^N-2) …^1
by using property -> A^ (a*b) = (A^a)^b

use modular exponentation to compute each A^N %P and then print ur answer

1 Like
#3

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MAX 100000

int power(ll x, ll y)
{
int temp;
if( y == 0)
return 1;
temp = power(x, y/2);
if (y%2 == 0)
return temptemp;
else
return xtemptemp;
}
int main()
{
ll t;
cin>> t;
while(t–)
{
ll a,n,p;
cin>> a>> n>> p;
ll ans=1,save=0;
//ll save=power(ans,n);
for(int i=1;i<=n;i++)
{
save=power(a,i);
cout<<save<<endl;
ans=(save%p);
cout<<ans<<endl;
}
ll real=ans%p;
cout<<real<<endl;

}

}

#4

Coding Blocks IDE

#5

i am getting WA in various question

#6

*test cases…

#7

@sunneykumar309
check now->

a) use long long everywhere to avoid overflow

b) use mod property (a * b)%mod=(a%mod * b %mod)%mod;

1 Like
#8

thankx bhai …

#9

still the error is same i am getting WA in 4/5 test cases.

#10

@sunneykumar309
bro whats the question name? i will try to submit it from my end

#11

ok question name is MATH DAY

#12

https://online.codingblocks.com/app/player/151917/content/169698/5281/code-challenge

#13

check ur power function, there u need to apply modulo as well to avoid overflow.
read about modular exponentiation for more details

#14

chekc now->

also check my very first response , i corrected the formula.

#15

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MAX 100000

/ll power(ll x, ll y) //changed int to ll
{
ll temp; //changed int to ll
if( y == 0)
return 1;
temp = power(x, y/2);
if (y%2 == 0)
return temptemp;
else
return xtemptemp;
} */
int power(int x, unsigned int y, int p)
{
int res = 1; // Initialize result

x = x % p; // Update x if it is more than or  
            // equal to p 

if (x == 0) return 0; // In case x is divisible by p; 

while (y > 0)  
{  
    // If y is odd, multiply x with result  
    if (y & 1)  
        res = (res*x) % p;  

    // y must be even now  
    y = y>>1; // y = y/2  
    x = (x*x) % p;  
}  
return res;

}
int main()
{
ll t;
cin>> t;
while(t–)
{
ll a,n,p;
cin>> a>> n>> p;
ll ans=a;
for(ll i=2;i<=n;i++)
{
ans=power(ans,i,p);
}
cout<<ans<<endl;

}

}

#16

Coding Blocks IDE

#17

still i am getting wrong answer

#18

pls check my last response, have already shared ur updated code.

  • use long long everywhere
#19

ok i got. it
…

#20

i have one more doubtin evaluating function
https://online.codingblocks.com/app/player/151917/content/169698/5109/code-challenge
in this q