Codeforces functionality may be limited from June 18, 19:00 (UTC) to June 19, 3:00 AM (UTC) due to technical maintenance. Polygon will work as usual. ×

### Loserinlife's blog

By Loserinlife, history, 12 months ago,

Calculate A^B mod C

A <= 10^100000

B <= 10^100000

C <= 10^9 (Doesn't have to be a prime number)

Thanks :)).

• +15

| Write comment?
 » 12 months ago, # | ← Rev. 4 →   +8 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) timeIn 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'.
•  » » 12 months ago, # ^ |   0 Oh thanks. I was looking for a mathematical approach for B but converting it into binary would work too :))
•  » » 12 months ago, # ^ | ← Rev. 2 →   0 Wait, but converting a number into binary would take log10(n) * log2(n) which would TLE in this case, right?
•  » » » 12 months ago, # ^ |   +3 No it will take only log2(b). Precisely I think you meant inputting as a string takes log10(b) and converting takes log2(b), so the total time taken is log10(b)+log2(b), not log10(b)*log2(b)
•  » » » » 12 months ago, # ^ | ← Rev. 3 →   +7 How would you impmement big integer base conversion in $O(n)$ (where $n$ is the length of the integer to be converted)? Because I'm quite sure that it is not possible. The best I could find was $O(n \log^2 n)$ described here.But technically we don't need to convert the base of $B$, we can instead use a modified version of binary exponentiation that goes one digit at a time on the base 10 representation and does up to 20 single multiplications on each step. If you don't understand my idea, I can add a code snippet of my method.UPD: Codeusing ll = long long; const ll m = 1000000007; ll modpow(ll a, string& b) { ll r = 1; for (char c : b) { ll r2 = r; for (int i = 0; i < 9; ++i) r = r * r2 % m; c -= '0'; for (int i = 0; i < c; ++i) r = r * a % m; } return r; } 
•  » » » » » 12 months ago, # ^ |   0 That would be great! I have never heard of that variation of binary exponentiation
•  » » » » » » 12 months ago, # ^ | ← Rev. 2 →   0 I updated my previous comment with the code.I haven't heard of it either; I just came up with it because it was an easy way to solve your problem.My solution is coded iteratively and not recursively. It relies on the same idea as typical binary exponentiation, just in base 10:Suppose $B = 12345$.Now, $A^B = A^{12345}$$= A^{12340} \cdot A^{5}$$= (A^{1234})^{10} \cdot A^{5}$and now we can calculate $A^{1234}$ recursively using the same method. But instead of doing recursion, I implemented the same thing iteratively starting from the other end.Now that I think about it, you could also do it recursively like this: Codeusing ll = long long; const ll m = 1000000007; ll modpow(ll a, string& b) { if (b.empty()) return 1; char c = b.back(); b.pop_back(); ll r = modpow(a, b); ll r2 = r; for (int i = 0; i < 9; ++i) r = r * r2 % m; c -= '0'; for (int i = 0; i < c; ++i) r = r * a % m; return r; } 
•  » » » » » 12 months ago, # ^ |   0 Yes, and beware: python int() function runs in quadratic
•  » » » » » 12 months ago, # ^ | ← Rev. 2 →   +1 Yes sorry... really have got into the bad habit of not considering logarithms sometimes.... 'Cause they generally they don't matter too much in cp solutions (I mean questions giving AC in O(n) mostly give AC in O(nlogn) too as n is generally upto 1e5 or 1e6).But thanks for the clarification
 » 12 months ago, # | ← Rev. 2 →   -12 ok.
•  » » 12 months ago, # ^ |   +7 Look at constraints
 » 12 months ago, # | ← Rev. 14 →   -6 First the input will be taken as string. Convery the given numbers in binary then take xor Iterate through the string and and at each step remainder can be calculated as Code snippetlets reminder be ans and string obtain after taking xor be s and C from which mod have to be taken for(int i = 0; i < s.size(); i++) { ans = (ans * 10 + s[i] — '0') % C; }
 » 12 months ago, # | ← Rev. 5 →   +59 If $B<\phi(C)$ then $A^B \bmod C = (A \bmod C)^{B} \bmod C$ If $B≥\phi(C)$ then $A^B \bmod C = (A \bmod C)^{\phi(C) + (B \bmod \phi(C))} \bmod C$ $\phi$ here denotes the euler toient function The above is true for All $C$You can calculate : $\phi(C)$ in $O(\sqrt C)$ $A \bmod C$ in $O(\log_{10}A)$ $B \bmod \phi(C)$ in $O(\log_{10}B)$ with also determining whether $B<\phi(C)$ or $B≥\phi(C)$ $A^B \bmod C$ in $O(\log_{2}\phi(C))$ using the new information above
•  » » 12 months ago, # ^ |   +16 Thanks! It works :))
•  » » » 12 months ago, # ^ |   +14 You are welcome