sabertooth's blog

Is SOD(A^b) % mod == SOD(bigmod(A,b,mod))?
By sabertooth, history, 7 years ago, In English

I have to calculate A^b where A^b can be a huge number then find The SOD(Sum of divisors) of that number.

So, If I calculate SOD(bigmod(A,b,mod)) will this return the same value as SOD(A^b) % mod

Asking for this As I am getting WA and could not get where I mistaken...

Link to the Problem

  • Vote: I like it
  • -3
  • Vote: I do not like it

»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

if you take the modulus of the power you may lose and gain new factors. Therefore it's false, the sum isn't guaranteed to be the same.

For example say your mod is 63, and you take 2^6, obviously your SOD for the modulus'd power will be 1, but the answer is much bigger.

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

    then how to calculate SOD(A^b) % mod? when A is prime?

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

      You can read the editorial, it is on the problem page

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

        Editorial shows the derivation of the formula..not the way to calculate SOD(A^b) Anyway thanks

        → Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

See: Multiplicative Function

The required function result(n) can be proved to be a multiplicative function, as if we define F(x)=σ1(x) and G(x)=1 (they're both multiplicative functions), the condition [result(x)=sigma(F(d)G(x/d) for all d|x)] helds(Convolution).

So we only need to calculate result(pi^ki) in a short time(e.g. O(1) or O(log m)), then simply multiply them.

It's obvious that

result(pi^ki)=1+(1+pi)+(1+pi+pi^2)+...+(1+pi+pi^2+...+pi^ki)

=(ki+1)*1+ki*pi+(ki-1)*pi^2+...+1*pi^ki

So, pi*result(pi^ki)=(ki+1)*pi+ki*pi^2+...+2*pi^ki+1*pi^(ki+1)

Their difference(i.e. (pi-1)*result(pi^ki)) equals to

-(ki+1)+pi+pi^2+pi^3...+pi^ki+pi^(ki+1)

=(pi^(ki+2)-1)/(pi-1)-(ki+2)

That is, result(pi^ki)=(pi^(ki+2)-1)/(pi-1)^2-(ki+2)/(pi-1)

Overall, result(n)=PI((pi^(a+i+2)-1)*inv(pi-1)^2-(a+i+2)*inv(pi-1) for each 1<=i<=m), where inv(x)=the inverse element of x MODULO 1e9+7.

→ Reply