blackapple's blog

Editorial: 185D: Visit of the Great
By blackapple, 12 years ago, In English

Problem 185D: Visit of the Great

A brief summary of the problem:

find LCM(k^(2^(i))+1(L<=i<=R)) mod p where p is a prime;

Solution:

Suppose Gi=k^(2^(i));

<1> for any different i and j,

it can be proved that:

a. if k is odd, GCD(Gi+1,Gj+1)=2

b. if k is even, GCD(Gi+1,Gj+1)=1

so:

a. if k is odd, ANS=2*PI((Gi+1)/2)
                   =PI(Gi+1) / 2^(R-L)

b. if k is even, ANS=PI(Gi+1)   (L<=i<=R)

<2>

Now, we want to find out PI(Gi+1) as quickly as possible:

Because: PI(Gi+1) = (G(R+1)-1)/(G(L)-1), (L<=i<=R)

we should calculate the right part of the equation.

<3>

Suppose (G(R+1)-1)/(G(L)-1) mod p = A

and there exits (G(L)-1) * B mod p = 1， (A and B are unknown).

Multipy the equations above:

A * 1 mod p = (G(R+1)-1) * B

i.e. (G(R+1)-1) * B mod p = A;

But how to find out B?

According to EULER's theory, EULER(p)=p-1 and k^(EULER(p)) mod p = 1 (p is a prime)

Thus, for any k and B which fulfills that k*B mod p = 1

B = k^(EULER(p)-1) = k^(p-2)

<4> One more thing: to calculate Gi fast, we need to get familiar with Fermat's Little Theorem:

a^(p-1) mod p = 1 (p is a prime)

Thus, a^Y mod p = a^(Y mod (p-1)) mod p;

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

»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice analysis!

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

why PI(Gi+1) = (G(R+1)+1)/(G(L)-1) I think it should be G(R+1)-1

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

    Oops, yes, you are right. It should be (G(R+1)-1)/(G(L)-1). I'll correct it. Thanks.~

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

hey,I'm new here and a very low quality programmer in here i didn't understand what did you mean by PI ,G(R+1), G(L) this things. So please don't mind if i'm bothering you. I would be grateful if you give me the answer

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

    I'd be glad to answer that~~. Actually, I'm not familiar with the tools to paste formulas in the test, so the formulas here are not quit recognizable; For pi(xi)(L<=i<=R), that is x(L) * x(L+1) * x(L+2) ... * X(R) ,all in the parentheses are subscripts.. it is something like sigma(xi)(L<=i<=R), which equals x(L)+....+x(R) More formally, pi(xi) is the products of all x(i) which has the subscript between L and R; and for Gi. i have defined it above, just for convenience: Gi=k^(2^(i)); That is ,Gr=k^(2^(r))

    → Reply