TheSleepyDevil's blog

By TheSleepyDevil, history, 3 weeks ago, In English

Given n , k , find the number of pairs (i,j) such that 0<=i<j<=n and k divides (j-i) Testcases up to 1e5 , (k<=n) up to 1e9 Sample:- input (5,2) , output 6

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by TheSleepyDevil (previous revision, new revision, compare).

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

i had an idea where the answer is just summation ((n)/k) + ((n-1)/k) + ... till n is k-1 , but idk if that's true or not , or how to calculate it fast

»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Let j-i=q*k

j-i=x

x=k,2*k,3*k....,(n/k)*k

Let n/k=t (integer division)

n>=j>=x

Number of solutions is n-k+1+(n-2*k+1)+(n-3*k+1)...(n-t+1)=n*t+t-k*t*(t+1)/2

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

    can u explain a bit more ?

    UPD: nvm , got it , thanks <3

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      j-i is multiple of k

      All multiples of k<=n are k,2*k,3*k,,,t*k

      Let x=q*k

      j-i=x

      As i>=0 Hence j>=x

      also j<=n

      Number of such j is n-x+1

      x ranges from k,2*k,...t*k