[BOJ 16998] It’s a Mod, Mod, Mod, Mod World

16998번: It’s a Mod, Mod, Mod, Mod World

 

풀이가 적혀있던 노트를 겨우 찾아서 포스팅한다. ㅎㅎ ㅠ

 

 

풀이

 

$x\%m=x-(x/m)*m$ 임을 이용해 주어진 식을 변형하면 $ans=\frac{n(n+1)}{2}p-q\sum_{i=1}^{n}\left \lfloor \frac{pi}{q} \right \rfloor$ 이다.

여기서 $\sum_{i=1}^{n}\left \lfloor \frac{pi}{q} \right \rfloor$ 을 $O(logN)$ 안에 구하는 것이 우리의 목적이다.

먼저, $p$와 $q$의 대소 관계를 고정시키기 위해 $p$를 $q$보다 작게 만들어주자. → $\sum_{i=1}^{n}\left \lfloor \frac{pi}{q} \right \rfloor =\frac{n(n+1)}{2}\left \lfloor \frac{p}{q} \right \rfloor+\sum_{i=1}^{n}\left \lfloor \frac{(p\%q)i}{q} \right \rfloor$

그리고 $\sum_{i=1}^{n}\left \lfloor \frac{pi}{q} \right \rfloor$ 을 해석적으로 바라보면 $y=\frac{p}{q}x$, $y=0$, $x=n$ 으로 둘러싸인 자연수 격자점의 수와 같다는 것을 알 수 있다.

하지만 이 격자점의 수를 한 번에 구하는 것은 쉽지 않으니, 큰 직사각형에서 다른 쪽 삼각형 내의 격자점의 수를 빼서 구하자.

전체 직사각형 내의 격자점의 수에 대한 식은 $\sum_{i=1}^{n}\left \lfloor \frac{pi}{q} \right \rfloor+\sum_{i=1}^{\left \lfloor \frac{pn}{q} \right \rfloor}\left \lfloor \frac{qi}{p} \right \rfloor-\left \lfloor \frac{n}{q} \right \rfloor=n\left \lfloor \frac{pn}{q} \right \rfloor$ 이다. ($p$와 $q$는 서로소임에 주의하자.)

위의 두 식을 이용해 격자점의 수를 재귀적으로 구하면 $p$, $q$, $n$이 모두 유클리드 호제법처럼 작아지기 때문에 대략 $O(logN)$에 해결할 수 있다.

 

코드

 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll solve(ll p,ll q,ll n) {
	if(!p) return 0;
	if(p>=q) return n*(n+1)/2*(p/q)+solve(p%q,q,n);
	return n*(p*n/q)+n/q-solve(q,p,p*n/q);
}
int main()
{
    cin.tie(0)->sync_with_stdio(0);
	int tc; cin >> tc;
	while(tc--){
		ll p,q,n; cin >> p >> q >> n;
		ll g=gcd(p,q);
		cout << n*(n+1)/2*p-q*solve(p/g,q/g,n) << '\n';
	}
}