TheSleepyDevil's blog

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

»
2 years ago, hide # |
 
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
»
2 years ago, hide # |
 
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
»
2 years ago, hide # |
 
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