No.315 世界のなんとか3.5

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 256 MB / 通常問題
タグ : / 解いたユーザー数 30
作問者 : koyumeishikoyumeishi

2 ProblemId : 766 / 出題時の順位表

注意

言語によっては実行時間制限キツイっぽいです。C++/Java/C#等の速い言語で解くことを推奨します。

参考

  • C++は特に意識して頑張らなくても 442 ms で通ってます。
  • Java素人のwriterがJavaで頑張ってみて 1118 ms で通ってます。
  • C#素人のwriterがC#で頑張ってみて1~2ケースTLEだったので、camypaperさんの入出力メソッドをコピペしたら 1747 ms で通りました。
  • python素人のwriterがpypyで頑張ってみてもダメでした(TLE)。 → もう少し工夫したら1.2secぐらいで通りました。 python3で通してる方も何人かいます。

問題文

ある芸人のモノマネをする芸人が現れました。
彼は「3の倍数 もしくは 3のつく数」のとき「アホ」になり、「$P$の倍数($P$は 8, 80, 800 のいずれか)」のとき「恥じらい」を見せます。
$A$ 以上 $B$ 以下の整数のうち、「アホ」になりかつ「恥じらい」を見せない数がいくつあるかを $10^9+7$ で割った時の余りで求めてください。

入力

A B P

入力はすべて整数で与えられる。
$1 \leq A \leq B \leq 10^{200000} = 10^{2 \times 10^5}$
$P$は 8, 80, 800 のいずれか

出力

$A$ 以上 $B$ 以下の整数のうち、「アホ」になりかつ「恥じらい」を見せない数がいくつあるかを $10^9+7$ で割った時の余りで出力してください。

サンプル

サンプル1
入力
1 100 8
出力
40

サンプル2
入力
114 514 80
出力
235

サンプル3
入力
1234 567890 800
出力
384205

提出ページヘ