# 「LCM・パレード」問題
# kとn以下の自然数mとが互いに素ならm自体を加算
# 1より大きい公約数があればmとの差分が生じる。
# mod kが同じm同士の規則性に着目して上記差分の合計を
# 算出し、1~nの合計から差し引いて答えを得た。
use strict;
use warnings;
my ($n, $k) = split(/\s+/, <>);
my @primes = (2, 3, 5);
my %factors = %{factorize($k)};
my $sum = ($n * ($n + 1)) >> 1;
my %gcm_table;
for my $f (keys(%factors)) { my $inc = 1;
for (1 .. $factors{$f}) {
$inc *= $f;
for (my $m = $inc; $m <= $k; $m += $inc) {
$gcm_table{$m} //= 1;
$gcm_table{$m} *= $f;
}
}
}
for my $m (keys(%gcm_table)) { next if ( $n < $m );
my $gcm = $gcm_table{$m};
my $initial_term = $m - $m / $gcm;
my $common_diff = $k - $k / $gcm;
my $num_of_terms = int(($n - $m) / $k) + 1; my $decrement = $num_of_terms * $initial_term + $common_diff * (($num_of_terms * ($num_of_terms - 1)) >> 1);
$sum -= $decrement;
}
sub factorize {
my %factors;
for (my $i = 0; $kk > 1; ++$i) {
# 素数リスト不足を補う
while ($i > $#primes) {
my $may_prime = $primes[-1];
while (1) {
$may_prime += 2;
my $is_prime = 1;
# 偶数は除外しているので3以降の素数で検証
for (my $j = 1; $may_prime >= $primes[$j] * $primes[$j]; ++$j) {
next if ($may_prime % $primes[$j]);
$is_prime = 0;
last;
}
if ($is_prime) {
push @primes, $may_prime; last;
}
}
}
# 素因数分解
my $prime = $primes[$i];
while (1) {
last if ($kk % $prime);
$factors{$prime} //= 0;
$factors{$prime} += 1;
$kk /= $prime;
}
if ($kk < $prime * $prime) {
$factors{$kk} = 1;
$kk = 1;
}
}
}
IyDjgIxMQ03jg7vjg5Hjg6zjg7zjg4njgI3llY/poYwKIyBr44GobuS7peS4i+OBruiHqueEtuaVsG3jgajjgYzkupLjgYTjgavntKDjgarjgolt6Ieq5L2T44KS5Yqg566XCiMgMeOCiOOCiuWkp+OBjeOBhOWFrOe0hOaVsOOBjOOBguOCjOOBsG3jgajjga7lt67liIbjgYznlJ/jgZjjgovjgIIKIyBtb2Qga+OBjOWQjOOBmG3lkIzlo6vjga7opo/liYfmgKfjgavnnYDnm67jgZfjgabkuIroqJjlt67liIbjga7lkIjoqIjjgpIKIyDnrpflh7rjgZfjgIExfm7jga7lkIjoqIjjgYvjgonlt67jgZflvJXjgYTjgabnrZTjgYjjgpLlvpfjgZ/jgIIKdXNlIHN0cmljdDsKdXNlIHdhcm5pbmdzOwoKbXkgKCRuLCAkaykgPSBzcGxpdCgvXHMrLywgPD4pOwoKbXkgQHByaW1lcyA9ICgyLCAzLCA1KTsKCm15ICVmYWN0b3JzID0gJXtmYWN0b3JpemUoJGspfTsKCm15ICRzdW0gPSAoJG4gKiAoJG4gKyAxKSkgPj4gMTsKbXkgJWdjbV90YWJsZTsKCmZvciBteSAkZiAoa2V5cyglZmFjdG9ycykpIHsKICAgIG15ICRpbmMgPSAxOwogICAgZm9yICgxIC4uICRmYWN0b3JzeyRmfSkgewogICAgICAgICRpbmMgKj0gJGY7CiAgICAgICAgZm9yIChteSAkbSA9ICRpbmM7ICRtIDw9ICRrOyAkbSArPSAkaW5jKSB7CiAgICAgICAgICAgICRnY21fdGFibGV7JG19IC8vPSAxOwogICAgICAgICAgICAkZ2NtX3RhYmxleyRtfSAqPSAkZjsKICAgICAgICB9CiAgICB9Cn0KCmZvciBteSAkbSAoa2V5cyglZ2NtX3RhYmxlKSkgewogICAgbmV4dCBpZiAoICRuIDwgJG0gKTsKCiAgICBteSAkZ2NtID0gJGdjbV90YWJsZXskbX07CiAgICBteSAkaW5pdGlhbF90ZXJtID0gJG0gLSAkbSAvICRnY207CiAgICBteSAkY29tbW9uX2RpZmYgPSAkayAtICRrIC8gJGdjbTsKICAgIG15ICRudW1fb2ZfdGVybXMgPSBpbnQoKCRuIC0gJG0pIC8gJGspICsgMTsKICAgIG15ICRkZWNyZW1lbnQgPSAkbnVtX29mX3Rlcm1zICogJGluaXRpYWxfdGVybSArICRjb21tb25fZGlmZiAqICgoJG51bV9vZl90ZXJtcyAqICgkbnVtX29mX3Rlcm1zIC0gMSkpID4+IDEpOwoKICAgICRzdW0gLT0gJGRlY3JlbWVudDsKfQoKcHJpbnQgJHN1bTsKCmV4aXQ7CgpzdWIgZmFjdG9yaXplIHsKICAgIG15ICRrayA9IHNoaWZ0OwogICAgbXkgJWZhY3RvcnM7CgogICAgZm9yIChteSAkaSA9IDA7ICRrayA+IDE7ICsrJGkpIHsKICAgICAgICAjIOe0oOaVsOODquOCueODiOS4jei2s+OCkuijnOOBhgogICAgICAgIHdoaWxlICgkaSA+ICQjcHJpbWVzKSB7CiAgICAgICAgICAgIG15ICRtYXlfcHJpbWUgPSAkcHJpbWVzWy0xXTsKICAgICAgICAgICAgd2hpbGUgKDEpIHsKICAgICAgICAgICAgICAgICRtYXlfcHJpbWUgKz0gMjsKICAgICAgICAgICAgICAgIG15ICRpc19wcmltZSA9IDE7CgogICAgICAgICAgICAgICAgIyDlgbbmlbDjga/pmaTlpJbjgZfjgabjgYTjgovjga7jgacz5Lul6ZmN44Gu57Sg5pWw44Gn5qSc6Ki8CiAgICAgICAgICAgICAgICBmb3IgKG15ICRqID0gMTsgJG1heV9wcmltZSA+PSAkcHJpbWVzWyRqXSAqICRwcmltZXNbJGpdOyArKyRqKSB7CiAgICAgICAgICAgICAgICAgICAgbmV4dCBpZiAoJG1heV9wcmltZSAlICRwcmltZXNbJGpdKTsKICAgICAgICAgICAgICAgICAgICAkaXNfcHJpbWUgPSAwOwogICAgICAgICAgICAgICAgICAgIGxhc3Q7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICBpZiAoJGlzX3ByaW1lKSB7CiAgICAgICAgICAgICAgICAgICAgcHVzaCBAcHJpbWVzLCAkbWF5X3ByaW1lOwogICAgICAgICAgICAgICAgICAgIGxhc3Q7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0KICAgICAgICB9CgogICAgICAgICMg57Sg5Zug5pWw5YiG6KejCiAgICAgICAgbXkgJHByaW1lID0gJHByaW1lc1skaV07CiAgICAgICAgd2hpbGUgKDEpIHsKICAgICAgICAgICAgbGFzdCBpZiAoJGtrICUgJHByaW1lKTsKICAgICAgICAgICAgJGZhY3RvcnN7JHByaW1lfSAvLz0gMDsKICAgICAgICAgICAgJGZhY3RvcnN7JHByaW1lfSArPSAxOwogICAgICAgICAgICAka2sgLz0gJHByaW1lOwogICAgICAgIH0KCiAgICAgICAgaWYgKCRrayA8ICRwcmltZSAqICRwcmltZSkgewogICAgICAgICAgICAkZmFjdG9yc3ska2t9ID0gMTsKICAgICAgICAgICAgJGtrID0gMTsKICAgICAgICB9CiAgICB9CiAgICByZXR1cm4gXCVmYWN0b3JzOwp9Cg==