ぱーぽーの競プロ記

競技プログラミングに関することを書きます。

ABC #020 D : LCM Rush

概要

2つの正整数a,bの最小公倍数をLCM(a,b)とする。

2つの正整数N,Kが与えられるので、{ \displaystyle \sum_{i=1}^{N} LCM(i,K)}を10^9+7で割った余りを求めよ。

  • 100点解法:1≦N≦10^9, 1≦K≦100
  • 101点解法:1≦N,K≦10^9

http://abc020.contest.atcoder.jp/tasks/abc020_d

解法

※本記事では100点解法のみ解説する。

1~Nまで全てのLCM(i, K)を愚直に求めている時間はないので工夫して計算する必要がある。

2つの正整数a,bの最大公約数をGCD(a,b)とすると、GCD(a, b) == GCD(b, a % b)という性質がある。

上記の性質はユークリッドの互除法(最大公約数を高速に求めるアルゴリズム)に基いている。
ユークリッドの互除法については蟻本にも書いてあるので詳しくはそちらを参照だが、このアルゴリズムは以下のような処理をしている。

ll gcd(ll a, ll b) {
  if(b == 0) return a;
  return gcd(b, a % b);
}

まさにGCD(a, b) == GCD(b, a % b)そのものだが、日頃C++の__gcd(a,b)を使っていて自分でgcdの処理を書いていないと意外と忘れてしまう。(反省)

この性質により、NをKで割った余り(0 ~ K-1)に分けてLCMの処理することができる。

NをKで割った余りをrとし、Kで割った余りがrとなるようなN以下の正整数は、初項r、公差K、項数nの等差数列に含まれる。
そしてその和Srを求めることで、LCMの和の一部を求めることができる。

あとはNをKで割った余り全てに対してこの処理を行い、全て足し合わせればよい。

ソースコード

#include <bits/stdc++.h>

#define REP(i, x, n) for(int i = x; i < (int)(n); i++)
#define rep(i, n) REP(i, 0, n)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define F first
#define S second
#define mp make_pair

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;

const ll mod = 1e9+7;

ll gcd(ll a, ll b) {
  if(b == 0) return a;
  return gcd(b, a % b);
}

int main() {
  // ios_base::sync_with_stdio(false);
  int N, K;
  cin >> N >> K;

  if(K > 100) return 0;

  ll ans = 0;
  REP(i, 1, K + 1) {
    if(N < i) break;
    ll n = N / K + (N % K >= i ? 1 : 0);
    ll a = i;
    ans += n * (2 * a + (n - 1) * K) / 2 * K / gcd(i, K);
    ans %= mod;

  cout << ans << endl;
  
  return 0;
}