TCO2015 Round2A 300. MODMODMOD

半分以上が赤で、日本人も激強の3人がいる圧倒的威圧感の部屋で、がんばって解いたのにunratedでツラい。ratedになった。

問題

要素がN個の配列mが与えられる。
ここで、f(x)=(((x mod m[0]) mod m[1]) ... mod m[N-1])とするとき、f(1)+...+f(R)の値を求めよ。

1<=N<=5000
1<=m[i]<=10^7
1<=R<=10^7

考え方

愚直に計算すると10^7*5000=5*10^10程度で完全にTLE。
計算を減らす方法を考える。

サンプル0を考えると、
0,1,2,3,4,5,6,7,8,9,10
に対してm[0]=5を適用すると、
0,1,2,3,4,0,1,2,3,4,0
と使われる数字がm[0]-1種類になる。

そこで、合計値を出す際、「ある数字の種類が何個あるか？」がわかっている場合を考える。
m[1]=3を考えると、
0が3個、1が2個、、、、4が2個というのがわかっている場合、m[1]=3を適用して影響を受けるのは、3,4になる。
3だったものは0になるので、0の個数に加算、4だったものは1になるので、1の個数に加算、のように計算できる。

こう計算する場合は、m[i]よりも大きい数字に対してのみになるので、最大でも10^7回で済む。