Euler Projesi 202. Soru

Üç ayna yansıtıcı yüzeyleri iç bölgeyi gösterecek şekilde bir eşkenar üçgen formunda yerleştirilmiştir (Şekil). Her köşede ise sadece bir lazer ışınının geçebileceği kadar büyüklükte boşluk bırakılmıştır.

Köşeleri A,B ve C olarak etiketlenen üçgende, bir lazer ışınının C köşesinden girip 11 kere yüzeyden yansıyıp tekrar aynı köşeden çıkabilmesinin 2 yolu vardır: bir yolu şekilde gösterilmiş, diğeri ise bunun tersi yöndedir.

Aynı şekilde C köşesinden giren bir lazer ışınının 1000001 kere yüzeylerden yansıyıp aynı köşeden çıkabilmesinin ise 80840 yolu vardır.

C köşesinden giren bir lazer ışınının 12017639147 kere yüzeylerden yansıyıp aynı köşeden çıkabilmesinin kaç yolu vardır?

Cevap: 1209002624
Örnek algoritma: C/C++

void euler202()
{
    const long long S = 6008819575;
    long long cnt = 0;

    long long n = 0;
    while (1)
    {
        long long N = 6*n+3;
        if (N >= S)
            break;
        if (N % 5 == 0) { n++; continue; }
        if (N % 11 == 0) { n++; continue; }
        if (N % 17 == 0) { n++; continue; }
        if (N % 23 == 0) { n++; continue; }
        if (N % 29 == 0) { n++; continue; }
        if (N % 41 == 0) { n++; continue; }
        if (N % 47 == 0) { n++; continue; }
        cnt++;
        n++;
    }
    cout << cnt*2 << endl;
}

Örnek algoritma: Mathematica

r = 12017639147;
n = (r + 3)/2;
t = Prepend[FactorInteger[n][[All, 1]], 3];
list = Table[
   Product[Subsets[t, {j}][[All, i]], {i, 1, j}], {j, 1, Length[t]}];
data = Table[Floor[n/list[[i]]], {i, 1, Length[list]}];
a = n - Sum[Total[data[[i]]] (-1)^(1 + i), {i, 1, Length[list]}];

t = FactorInteger[n][[All, 1]];
list = Table[
   Product[Subsets[t, {j}][[All, i]], {i, 1, j}], {j, 1, Length[t]}];
data = Table[Floor[n/(3 list[[i]])], {i, 1, Length[list]}];
b = Ceiling[(n - 1)/3] - 
   Sum[Total[data[[i]]] (-1)^(1 + i), {i, 1, Length[list]}];
a - b

Örnek algoritma: Matlab

v = [5 11 17 23 29 41 47] ;
u = 6008819574 ;
S = 0 ;

for n = 128:255
    
    w = binar(n) ;
    w(1) = [] ;
    m = prod(v .^ w) ;
    k = floor(u/m) ;
    
    if mod(m,3) == 1
        l = floor((k+1)/3) ;
    else
        l = floor((k+2)/3) ;
    end
    
    t = sum(w) ;
    
    S = S + l* (-1)^t ;
end

S

Örnek algoritma: Java

import java.util.Set;

import common.Common;

public class Problem202 {

    public static void main(String[] args) {
        System.out.println("Answer = "+getCount(12017639147L));
    }
    
    private static long getCount(long n) {
        long count = 0;
        long level = (n+1)/2 + 1;
        long cCount = 0;
        long cMod = level % 3 == 0 ? 0 : level % 3 == 1 ? 2 : 1;
        Set<Long> factors = Common.getFactors(level).keySet();
        for ( long i = 1 ; i < level ; i++ ) {
            cCount++;
            if ( cCount % 3 == cMod ) {
                boolean ok = true;
                for ( long divisor : factors ) {
                    if ( i % divisor == 0 ) {
                        ok = false;
                        break;
                    }
                }
                if ( ok )
                    count++;
            }
        }
        return count;
    }
}

Örnek algoritma: Delfi

procedure TForm1.PEuler202Click(Sender: TObject);
const
  factor:array[1..7] of Integer=(5,11,17,23,29,41,47);
  largest:Int64=6008819575;
var
  i,Sum:Integer; j:Int64;
begin
  j:=3; Sum:=0;
  while j<largest do
  begin
    for i:=1 to High(factor) do if j mod factor[i]=0 then break;
    if i>High(factor) then inc(Sum);
    inc(j,6);
  end;
  Memo1.Lines.Add(format('Sum = %d',[Sum*2]));
end;