裏 RjpWiki

Julia ときどき R, Python によるコンピュータプログラム,コンピュータ・サイエンス,統計学

「LCM・パレード」問題

2018年02月18日 | ブログラミング

「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

コメント    この記事についてブログを書く
  • X
  • Facebookでシェアする
  • はてなブックマークに追加する
  • LINEでシェアする
« 切手を切って! | トップ | 集合写真できれいに写る配置... »
最新の画像もっと見る

コメントを投稿

ブログラミング」カテゴリの最新記事