ABC020 D - LCM Rush

D - LCM Rush

概要

整数N, Kについて、LCM(1, K) + LCM(2, K) + … + LCM(N, K) を求めよ。

以下、100点解答です。（満点は101点）

制約

1 ≦ N ≦ 10^9
1 ≦ K ≦ 100

方針

重要な等式としてLCM(a, b) = a * b / GCD(a, b) が成り立つ。
するとLCM(1, K) + LCM(2, K) + … + LCM(N, K) は次の式と等しい。

2つめの和の計算については、GCDは周期性をもっており、GCD(a + b * d, d) = GCD(a, d)が成り立つ。
なので、MODが等しいものをグルーピングして等差数列の和として計算できる。
例：K=4, N = 11

i	1	2	3	4	5	6	7	8	9	10	11
GCD(i, K)	1	2	1	4	1	2	1	4	1	2	1

⇒
GCDごとに和を格納する配列aを準備する
i MOD K = 1のグループはGCD(i, K) = 1であるため、a[1]に1+5+9 を加算
i MOD K = 2 のグループはGCD(i, K) = 2であるため、a[2]に2+6+10を加算
i MOD K = 3 のグループはGCD(i, K) = 1であるため、a[1]に3+7+11を加算
i MOD K = 4 のグループはGCD(i, K) = 4であるため、a[4]に4+8を加算

解答

D - LCM Rush

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
 
ll gcd(ll a, ll b){
	if(b == 0) return a;
	return gcd(b, a % b);
}
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	ll MOD = 1e9+7;
 
	ll N, K;
	cin >> N >> K;
 
	if(K > 100){
		cout << -1 << endl;
		return 0;
	}
 
	if(N < K){
		ll ans = 0;
		for(int i = 1; i <= N; i++){
			ans += i * K / gcd(i, K);
		}
 
		cout << ans << endl;
		return 0;
	}
 
	ll q = N / K;
	ll r = N % K;
 
	vector<ll> a(K+1, 0);
	for(int i= 1; i <= K; i++){
		ll d = gcd(i, K);
		a[d] += q * (2 * i + K * (q - 1)) / 2;
		if(i % K != 0 && i % K <= r) a[d] += q * K + i;
		// cout << i << "," << d << "," << a[d] << endl;
		a[d] %= MOD;
	}
 
	// rep(i, K) cout << a[i+1] << ",";
	// cout << endl;
 
	ll ans = 0;
	for(int i = 1; i <= K; i++){
		ans += K * a[i] / i;
		ans %= MOD;
	}
 
	cout << ans << endl;
}