Loserinlife's blog

A^B mod C

By Loserinlife, history, 18 months ago, In English

Calculate A^B mod C

A <= 10^100000

B <= 10^100000

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

Thanks :)).

  • Vote: I like it
  • +15
  • Vote: I do not like it

Comments Comments (15)
| Write comment?
»
18 months ago, # |
← Rev. 4   Vote: I like it +8 Vote: I do not like it

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'.

→ Reply
  • »
    »
    18 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Oh thanks. I was looking for a mathematical approach for B but converting it into binary would work too :))

    → Reply
  • »
    »
    18 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Wait, but converting a number into binary would take log10(n) * log2(n) which would TLE in this case, right?

    → Reply
    • »
      »
      »
      18 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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)

      → Reply
      • »
        »
        »
        »
        18 months ago, # ^ |
        ← Rev. 3   Vote: I like it +7 Vote: I do not like it

        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:

        Code
        → Reply
        • »
          »
          »
          »
          »
          18 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          That would be great! I have never heard of that variation of binary exponentiation

          → Reply
          • »
            »
            »
            »
            »
            »
            18 months ago, # ^ |
            ← Rev. 2   Vote: I like it 0 Vote: I do not like it

            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:

            Code
            → Reply
        • »
          »
          »
          »
          »
          18 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yes, and beware: python int() function runs in quadratic

          → Reply
        • »
          »
          »
          »
          »
          18 months ago, # ^ |
          ← Rev. 2   Vote: I like it +1 Vote: I do not like it

          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

          → Reply
»
18 months ago, # |
← Rev. 2   Vote: I like it -12 Vote: I do not like it

ok.

→ Reply
»
18 months ago, # |
← Rev. 14   Vote: I like it -6 Vote: I do not like it

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 snippet
→ Reply
»
18 months ago, # |
← Rev. 5   Vote: I like it +59 Vote: I do not like it

  • 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

→ Reply