No.836 じょうよ

レベル : / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 176
作問者 : face4face4 / テスター : はむこはむこ
2 ProblemId : 2708 / 出題時の順位表
問題文最終更新日: 2019-06-14 19:10:59

問題文

閉区間 $[l,r]$ に含まれる整数を $n$ で割った余りで分類してください。

入力

$l$ $r$ $n$
  • $1 \le l \le r \le 10^{18}$
  • $1 \le n \le 10^5$
  • 入力は全て整数で与えられる

出力

$n$行出力してください。

$i$ 行目($1 \le i \le n$) には閉区間 $[l,r]$ に含まれる整数のうち、$n$ で割った余りが $i-1$ となるものの個数を出力してください。

大丈夫

出力が多め&時間制限が厳しめではありますが、python3で十分に余裕を持ってAC出来ることを確認しています。

サンプル

サンプル1
入力
1 7 2
出力
3
4

2で割った余りが0となる整数は2,4,6の3つ、1となる整数は1,3,5,7の4つです。

サンプル2
入力
1 1000000000000000000 11
出力
90909090909090909
90909090909090910
90909090909090909
90909090909090909
90909090909090909
90909090909090909
90909090909090909
90909090909090909
90909090909090909
90909090909090909
90909090909090909

入力・出力が32bit整数型に収まらないことがあります。

サンプル3
入力
5 5 1
出力
1

ヒント

$l$から$r$まで1つずつ愚直に計算していては埒が明かないので、工夫してどこか一部をまとめて計算することを考えてみましょう。

適当な$l,r,n$を用意して余りを書き並べてみると良いかもしれません。

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。