TheSleepyDevil's blog

Help In Math Problem
By TheSleepyDevil, history, 6 months 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

»
6 months 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).

→ Reply
»
6 months 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

→ Reply
»
6 months 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

→ Reply
  • »
    »
    6 months 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

    → Reply
    • »
      »
      »
      6 months 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

      → Reply