Euler Projesi 228. Soru

Minkowski Toplamları

$S_n$, $v_k (k=1,2,...,n)$ köşelerinin koordinatları

$x_k=cos(\frac{2k-1}{n} \times 180^o)$

$y_k=sin(\frac{2k-1}{n} \times 180^o)$

olan düzgün k-kenarlı bir çokgen -bir şekil- olsun.

Her  $S_n$ çokgeni, hem üzerindeki hem de iç bölgesindeki noktaları kapsayan birer şekil olarak tanımlanıyor.

İki S ve T şeklinin S+T Minkowski toplamı, S ile T'nin her noktasının koordinatsal olarak toplanmasıyla elde ediliyor: (u,v)+(x,y)=(u+x,v+y).

Örneğin $S_3$ ile $S_4$ şekillerinin toplamı aşağıda pembe renkle verilen altı-kenarlı şekildir:

$S_{1864}+S_{1865}+...+S_{1909}$ toplamı kaç kenarlıdır?

Cevap 86226.

C++:

 set < pair < int, int > > s;
 for (int i = 1864; i <= 1909; ++i) {
  for (int j = 0; j < i; ++j) {
   int t = GCD(i, j);
   s.insert(make_pair(j/t, i/t));
  }
 }
 ans = s.size();

Python:

def problem228():
    s = set()
    for n in xrange(1864, 1909 + 1):
        for i in xrange(n):
            s.add(Fraction(i, n))
    return len(s)

Mathematica:

L = {0};
For[n = 1864, n <= 1909, n++,
  Print[n];
  L1 = Table[i/n, {i, 1, n - 1}];
  L = Union[L, L1];
  ];
Length[L]

Haskell:

import Data.Ratio
import Data.List
import Data.Set

edge n = take n [0,1%n..] -- *2*pi
main = print . size . fromList . concatMap edge $ [1864..1909]

Perl:

#!/usr/bin/perl -l
for my $s(1864..1909) {
 for my $k(1..$s) {
  my $ch = 180*(2*$k-1);
  my $zn = $s;
  my $a  = Math::BigRat->new("$ch/$zn");
  my $b  = Math::BigRat->new("360/$zn");
  my $angle = $b-2*$a;
  $ANS{"$angle"}++;
 }
}

print scalar keys %ANS;