問題一覧 > 通常問題

No.3179 3 time mod

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 87
作問者 : Cafe1942 / テスター : tsunamayo123 kk2a sclara
ProblemId : 12338 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-06-13 19:47:00

問題文

$N$ 以下の非負整数のうち、 $P$ で割った余りが $A$ 、 $Q$ で割った余りが $B$ 、 $R$ で割った余りが $C$ であるような非負整数は何個ありますか。

制約

  • $0 \leq N \leq 10^{18}$
  • $1 \leq P,Q,R \leq 10^6$
  • $P,Q$は互いに素
  • $Q,R$は互いに素
  • $R,P$は互いに素
  • $0 \leq A < P$
  • $0 \leq B < Q$
  • $0 \leq C < R$
  • 与えられる入力はすべて整数

入力

$N$
$P$ $Q$ $R$
$A$ $B$ $C$

出力

最後に改行してください。

サンプル

サンプル1
入力
71
2 3 5
0 1 2
出力
2

割った余りが $3$ 個の条件を満たす数は、 $22$ $,$ $52$ $,$ $82$ $,...$ です。このうち、 $N ( = 71 )$ 以下であるようなものは、 $22$ $,$ $52$ の $2$ 個であるので、 $2$ を出力してください。

サンプル2
入力
2005
1 1 1
0 0 0
出力
2006

$1$ と $1$ は互いに素であることに注意してください。また、 $0$ が条件を満たす数となる可能性にも注意してください。

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