Блог пользователя Loserinlife

A^B mod C

Автор Loserinlife, история, 18 месяцев назад, По-английски

Calculate A^B mod C

A <= 10^100000

B <= 10^100000

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

Thanks :)).

  • Проголосовать: нравится
  • +15
  • Проголосовать: не нравится

»
18 месяцев назад, # |
← 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) 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'.

→ Ответить
  • »
    »
    18 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
  • »
    »
    18 месяцев назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      18 месяцев назад, # ^ |
        Проголосовать: нравится +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)

      → Ответить
      • »
        »
        »
        »
        18 месяцев назад, # ^ |
        ← 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:

        Code
        → Ответить
        • »
          »
          »
          »
          »
          18 месяцев назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

          → Ответить
          • »
            »
            »
            »
            »
            »
            18 месяцев назад, # ^ |
            ← 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:

            Code
            → Ответить
        • »
          »
          »
          »
          »
          18 месяцев назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

          → Ответить
        • »
          »
          »
          »
          »
          18 месяцев назад, # ^ |
          ← 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

          → Ответить
»
18 месяцев назад, # |
← Rev. 2   Проголосовать: нравится -12 Проголосовать: не нравится

ok.

→ Ответить
»
18 месяцев назад, # |
← 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 snippet
→ Ответить
»
18 месяцев назад, # |
← 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

→ Ответить