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

Is SOD(A^b) % mod == SOD(bigmod(A,b,mod))?
Автор sabertooth, история, 6 лет назад, По-английски

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

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

»
6 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
»
6 лет назад, # |
← Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

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.

→ Ответить