問題一覧 > 通常問題

No.836 じょうよ

レベル : / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 292
作問者 : face4face4 / テスター : はむこはむこ
8 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$を用意して余りを書き並べてみると良いかもしれません。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。