No.836 Jouyo (Remainder)
face4
はむこProblem Statement
Classify the integers contained in the closed interval $[l,r]$ by their remainder when divided by $n$.
Input
$l$ $r$ $n$
- $1 \le l \le r \le 10^{18}$
- $1 \le n \le 10^5$
- All inputs are integers.
Output
Output $n$ lines.
On the $i$-th line ($1 \le i \le n$), output the number of integers in the closed interval $[l,r]$ whose remainder when divided by $n$ is $i-1$.
Don't worry
The output is rather large & the time limit is rather strict, but we have confirmed that python3 can get AC with plenty of margin.
Sample
Sample 1
Input
1 7 2
Output
3 4
The integers with remainder 0 when divided by 2 are the 3 integers 2,4,6, and those with remainder 1 are the 4 integers 1,3,5,7.
Sample 2
Input
1 1000000000000000000 11
Output
90909090909090909 90909090909090910 90909090909090909 90909090909090909 90909090909090909 90909090909090909 90909090909090909 90909090909090909 90909090909090909 90909090909090909 90909090909090909
The input and output may not fit in a 32-bit integer type.
Sample 3
Input
5 5 1
Output
1
Hint
Computing naively one by one from $l$ to $r$ will get you nowhere, so try to find a way to compute some part of it all at once.
It may help to prepare some arbitrary $l,r,n$ and write out the remainders.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。