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

Help In Math Problem
Автор TheSleepyDevil, история, 5 месяцев назад, По-английски

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

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

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
5 месяцев назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    5 месяцев назад, # ^ |
    ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    can u explain a bit more ?

    UPD: nvm , got it , thanks <3

    → Ответить
    • »
      »
      »
      5 месяцев назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      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

      → Ответить