A^B mod C
source link: https://codeforces.com/blog/entry/117140
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
A^B mod C - Codeforces
Calculate A^B mod C
A <= 10^100000
B <= 10^100000
C <= 10^9 (Doesn't have to be a prime number)
Thanks :)).
The constraints on A and B seem quite large, but the way would be:
Note that (a^b)%c = ((a%c)^b)%c so,
1) Compute (a%c)
2) Use binary exponentiation to compute ((a%c)^b)%c in log(10^100000) time
In python, integers are infinite so u can directly calculate a%c and pow function implements binary exponentiation, so the ans would be simply pow(a%c,b,c).
In C++, where u have no bigint by default, u can input 'a' as a string, and do as follows:
string a;
cin>>a;
ll x,c,ans=0,p=1,n=a.size();
cin>>c;
for(int i=n-1;i>=0;--i){
x=a[i]-'0';
ans+=x*p%c,ans%=c;
p=p*10%c;
As for binary exponentiation you would need to input b as a string and convert it to a binary string. And then instead of the while(b>0) and b/=2 in the regular binary exponentiation, traverse b in the reverse order replacing the if condition (b%2==1) with b[i]=='1'.
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK