백준 24518 / C++

https://www.acmicpc.net/problem/24518

24518번: 잘 알려진 합 구하기

 

[ 풀이 ] 

몫이라는게 N에 가까워질수록 같은값이 점점 많아진다. 같은값이 나오는 구간을 묶어보자. 

[N/2+1, N] 은 몫이 모두 1이다. [N/3+1, N/2]은 몫이 모두 2이다. 

이렇게 구간 나누는걸 sqrt(N)이 나올때까지 한다. 

이제 sqrt(N)까진 그냥 f(i)g(i)를 계산하고 나머지 구간들은 몫이 같은 구간마다 나머지들을 곱해서 더해준다. 

여기서 그냥 훑으면서 계산하면 O(N)이다. 나머지는 0, 1, ...., m-1이 반복된다는 성질을 통해, 

구간마다 주기를 찾고 잘 처리해주면 O(1)로 가능하다. 이 부분 구현이 살짝 어려웠다. 

 

[ Code ] 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll n, m, MOD = 1e9 + 7;

// return 0%m+1%m+...+x%m
ll sum(ll x) {
	ll ret = 0;
	ll T = (x + 1) / m; // 0~m-1이 포함된 구간의 개수
	ret += T * m * (m - 1) / 2; // 그 구간들의 합 
	ll st = T * m; // 나머지 시작 인덱스
	ret += (x - st) * (x - st + 1) / 2;
	return ret;
}

ll solve(ll n, ll m) {
	ll ret = 0;
	int sqn = sqrt(n);
	// sqrt(n)까지 계산 O(sqrt(N))
	for (int i = 1; i <= sqn; i++) {
		ret = (ret + (n / i) * (i % m)) % MOD;
	}
	// [N/(i+1)+1, N/i]마다 계산하기  O(sqrt(N))
	for (int i = 1; i + 1 <= n / sqn; i++) {
		ret = (ret + i * (sum(n / i) - sum(n / (i + 1)))) % MOD;
	}
	return ret;
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m;
	cout << solve(n, m) << '\n';
}