바닥의 무게중심
다이아몬드 II의견: 0
음이 아닌 정수 \(n, m, a, b\)가 주어진다 (\(m \ge 1\)). 다음 두 값을 구하라.
$$ A = \sum_{i=0}^{n-1} \left\lfloor \frac{a \cdot i + b}{m} \right\rfloor $$
$$ B = \sum_{i=0}^{n-1} i \cdot \left\lfloor \frac{a \cdot i + b}{m} \right\rfloor $$
여기서 \(\lfloor x \rfloor\)는 \(x\) 이하의 최대 정수를 뜻한다.
총 \(T\)개의 질의가 주어지며, 각 질의마다 \((n, m, a, b)\)가 독립적으로 주어진다. \(A\)와 \(B\)는 매우 커질 수 있으므로 각각을 \(998244353\)으로 나눈 나머지로 출력한다.
\(n\)이 최대 \(10^9\)에 달하므로 \(i\)를 일일이 순회하는 방법으로는 제한 시간 안에 풀 수 없다.
\(1 \le T \le 10^5\)
\(0 \le n \le 10^9\)
\(1 \le m \le 10^9\)
\(0 \le a, b \le 10^9\)
첫 줄에 질의의 수 \(T\)가 주어진다.
이어지는 \(T\)개의 줄에 각각 네 정수 \(n\), \(m\), \(a\), \(b\)가 공백으로 구분되어 주어진다.
각 질의마다 한 줄에 두 정수 \(A \bmod 998244353\) 와 \(B \bmod 998244353\) 를 공백으로 구분하여 출력한다.
3
5 3 2 1
4 2 3 0
1 1 0 0
7 21
8 19
0 0첫 질의 n=5,m=3,a=2,b=1: floor((2i+1)/3) = [0,1,1,2,3] (i=0..4). A=0+1+1+2+3=7, B=00+11+12+23+3*4=0+1+2+6+12=21.
둘째 질의 n=4,m=2,a=3,b=0: floor(3i/2)=[0,1,3,4], A=8, B=0+1+6+12=19.
셋째 질의 n=1: i=0만 존재, floor(0)=0, A=0, B=0.
2
0 7 5 3
10 4 4 4
0 0
55 330첫 질의 n=0: 합이 없으므로 A=0, B=0.
둘째 질의 n=10,m=4,a=4,b=4: floor((4i+4)/4)=floor(i+1)=i+1 = [1,2,...,10]. A=55, B= sum i*(i+1) = 0+2+6+12+20+30+42+56+72+90 = 330.
riseoj 작성
출처 Original
평가 및 의견
바닥의 무게중심
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
바닥의 무게중심