fork(2) download
  1. # 「LCM・パレード」問題
  2. # kとn以下の自然数mとが互いに素ならm自体を加算
  3. # 1より大きい公約数があればmとの差分が生じる。
  4. # mod kが同じm同士の規則性に着目して上記差分の合計を
  5. # 算出し、1~nの合計から差し引いて答えを得た。
  6. use strict;
  7. use warnings;
  8.  
  9. my ($n, $k) = split(/\s+/, <>);
  10.  
  11. my @primes = (2, 3, 5);
  12.  
  13. my %factors = %{factorize($k)};
  14.  
  15. my $sum = ($n * ($n + 1)) >> 1;
  16. my %gcm_table;
  17.  
  18. for my $f (keys(%factors)) {
  19. my $inc = 1;
  20. for (1 .. $factors{$f}) {
  21. $inc *= $f;
  22. for (my $m = $inc; $m <= $k; $m += $inc) {
  23. $gcm_table{$m} //= 1;
  24. $gcm_table{$m} *= $f;
  25. }
  26. }
  27. }
  28.  
  29. for my $m (keys(%gcm_table)) {
  30. next if ( $n < $m );
  31.  
  32. my $gcm = $gcm_table{$m};
  33. my $initial_term = $m - $m / $gcm;
  34. my $common_diff = $k - $k / $gcm;
  35. my $num_of_terms = int(($n - $m) / $k) + 1;
  36. my $decrement = $num_of_terms * $initial_term + $common_diff * (($num_of_terms * ($num_of_terms - 1)) >> 1);
  37.  
  38. $sum -= $decrement;
  39. }
  40.  
  41. print $sum;
  42.  
  43.  
  44. sub factorize {
  45. my $kk = shift;
  46. my %factors;
  47.  
  48. for (my $i = 0; $kk > 1; ++$i) {
  49. # 素数リスト不足を補う
  50. while ($i > $#primes) {
  51. my $may_prime = $primes[-1];
  52. while (1) {
  53. $may_prime += 2;
  54. my $is_prime = 1;
  55.  
  56. # 偶数は除外しているので3以降の素数で検証
  57. for (my $j = 1; $may_prime >= $primes[$j] * $primes[$j]; ++$j) {
  58. next if ($may_prime % $primes[$j]);
  59. $is_prime = 0;
  60. last;
  61. }
  62. if ($is_prime) {
  63. push @primes, $may_prime;
  64. last;
  65. }
  66. }
  67. }
  68.  
  69. # 素因数分解
  70. my $prime = $primes[$i];
  71. while (1) {
  72. last if ($kk % $prime);
  73. $factors{$prime} //= 0;
  74. $factors{$prime} += 1;
  75. $kk /= $prime;
  76. }
  77.  
  78. if ($kk < $prime * $prime) {
  79. $factors{$kk} = 1;
  80. $kk = 1;
  81. }
  82. }
  83. return \%factors;
  84. }
  85.  
Success #stdin #stdout 0s 17768KB
stdin
10 3
stdout
43