「LCM・パレード」問題
締め切りが 2018/02/18 10:00 AM なので,その 1 分後に投稿されるように予約
自然数 a, b に対し、a と b の最小公倍数を LCM(a, b) と定義します。
例えば、LCM(6, 8)=24 です。
さらに、自然数 n, k に対し、n 以下の全ての自然数 m に対する LCM(k, m)÷k の値の和を F(n, k)と定義します。
例えば F(9, 12)=22 です。以下の表の最下列の数の和です。
同様に、F(10, 3)=43, F(20, 9)=162 となることが確かめられます。
標準入力から、自然数 n と k (1 ≦ n ≦ 10^8, 1 ≦ k ≦ 10^5)が半角空白区切りで与えられます。
標準出力に F(n, k) の値を出力するプログラムを書いてください。
===== ===== ===== ===== ===== =====
末尾に示す素直な R プログラムでは,n が大きくなると計算時間が掛かりすぎる。
なぜわざわざ LCM(k, n)/k なんて使うのだ?というところに実はヒントがあるのだろう。
k = 50 のときの LCM(50, m)/50, m=1, 2, ..., 50 を書き出してみれば,以下のようになる。
つまり,和を求める数値 LCM(k, m)/k は,m が k の素因数で割り切れるときにはその値で割る(同じ素因数が複数個ある場合も同様に)。
これらの和をとったものが F(n, k) である。
この方針で R プログラムを書いても,さすがに n = 100000000 では時間制限にひっかかる。
C で書き直して OK となるが,R プログラムは簡潔。
divisor = function(n) {
for (i in 2:sqrt(n)) {
if (n %% i == 0) {
return(i)
}
}
return(n)
}
f = function(n, k) {
x = as.numeric(1:n)
while (k > 1) {
div = divisor(k)
if (n >= div) {
i = 1:(n %/% div)*div
x[i] = ifelse(x[i] %% div == 0, x[i] / div, x[i])
}
k = k/div
}
options(scipen=100)
cat(sum(x))
}
f(9, 12) # 22
f(40, 50) # 502
f(312, 41) # 47708
f(7122, 360) # 10778909
system.time(f(1234567, 17200)) # 414701577895, 0.318 s
system.time(f(98777, 98999)) # 4878497253, 0.001 s
system.time(f(100000000, 98765)) # 4199787396686968, 2.080 s
C プログラム
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int divisor(int n) {
for (int i = 2; sqrt(n) >= i; i++) {
if (n%i == 0) {
return i;
}
}
return n;
}
double f(int n, int k) {
int i;
int x[n+1];
for (i = 1; n >= i; i++) {
x[i] = i;
}
while (k > 1) {
int div = divisor(k);
for (i =1; n / div >= i; i++) {
int i2 = i*div;
if (x[i2] % div == 0) {
x[i2] /= div;
}
}
k /= div;
}
double sum = 0;
for (int i = 1; n >= i; i++) {
sum += x[i];
}
return sum;
}
int main() {
int n, k;
scanf("%d %d", &n, &k);
printf("%.0f\n", f(n, k));
return 0;
}
簡単に書けるが,遅い R プログラム
LCM = function(m, n) {
n0 = n
while ((temp = n %% m) != 0) {
n = m
m = temp
}
n0/m
}
f = function(n, k) {
sum = 0
for (m in 1:n) {
sum = sum+LCM(k, m)
}
options(scipen=100)
cat(sum)
}
#arg = scan(file("stdin", "r"))
#f(arg[1], arg[2])
f(9, 12) # 22
#f(40, 50) # 502
#f(312, 41) # 47708
#f(7122, 360) # 10778909
#system.time(f(1234567, 17200)) # 414701577895, 2.831 s
#f(98777, 98999) # 4878497253
#system.time(f(100000000, 98765)) # 4199787396686968, 298.946 s
最新の画像[もっと見る]
- さぬきうどん 山よし 佐文店 12時間前
- さぬきうどん 山よし 佐文店 12時間前
- 算額(その1394) 23時間前
- 算額(その1393) 1日前
- 和算の心(その008) 1日前
- ぶっかけうどん はな庄 2日前
- ぶっかけうどん はな庄 2日前
- 晴屋製麺所 2日前
- 晴屋製麺所 2日前
- 算額(その1391) 3日前
※コメント投稿者のブログIDはブログ作成者のみに通知されます