Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

ak3899's blog

By ak3899, history, 3 months ago, In English,

recently i encountered with this problem on spoj spoj_link problem : https://www.spoj.com/problems/INS17M/ Someone help how to solve it please!!

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

»
3 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

GCD(Fi, Fj) = FGCD(i, j)

  • »
    »
    3 months ago, # ^ |
    Rev. 2   Vote: I like it +4 Vote: I do not like it

    GCD(Fi, Fj) = ... :'v

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

      if it's GCD(fi,fj)=GCD(i,j) so we should not calculate the fib part except the pow(A[i],k) am i right?

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

      that's not true...

      if i = 2, j = 4, GCD(fi, fj) = GCD(1, 3) = 1, not 2.

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

    can you please elaborate once again in detail.

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

      so fibonaaci's part doesnt matter :)

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

      it was wrong edited it..

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

        sorry, you're right

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

        i know this lemma already but how to implement it because constraint is 0 < N <= 100000 how i gonna find the all pairs please help if you have fully solved this problem ? please provide pseudocode if possible.