Euler Projesi 281. Soru

Pizza Malzemeleri

Size m · n eşit parçaya kesilmiş bir pizza (mükemmel daire) veriliyor ve her dilimde tam olarak bir malzeme olmasını istiyorsunuz.

F(m, n) pizzayı, m farklı malzeme (m ≥ 2) ile, her bir malzemeyi tam olarak n dilimde (n ≥ 1) kullanarak yapabileceğiniz yolların sayısını göstersin. Yansımalar farklı kabul edilirken rotasyonlar farklı kabul edilmemektedir.

Böylece, örneğin, f (2,1) = 1, f (2,2) = f (3,1) = 2 ve f (3,2) = 16.

f (3,2) aşağıda gösterilmiştir:

F (m, n) ≤ 10¹⁵ olacak şekilde tüm f (m, n) toplamlarını bulunuz.

Cevap: 1485776387445623
Fortran: program p281 implicit none integer,parameter:: LONG=SELECTED_INT_KIND(16) integer(LONG),parameter:: LIMIT=10_LONG**15 integer(LONG):: m,n,ff integer(LONG):: s=0 real:: mfak,fprev,fcurr m=1 mfak=1 do m=m+1 mfak=mfak*(m-1) if (mfak>LIMIT) exit ! f(m,1)=(m-1)! n=0 fcurr=1 do n=n+1 ff=f281(m,n) if (ff<=LIMIT .and. ff>0) then s=s+ff else exit end if fprev=fcurr fcurr=ff if (fcurr/fprev*ff>LIMIT) exit end do end do write(*,*) s contains integer(LONG) function f281(m,n) implicit none integer(LONG):: m,n f281=f(m,n,n)/m end function f281 integer(LONG) recursive function f(m,n,p) result(ff) implicit none integer(LONG):: m,n,p ! number of colors, sections, symmetries integer(LONG):: p1,p2,q(p) if (m==1) then ff=1 else if (p==1) then ff=C(m*n,n)*f(m-1,n,p) else ff=0 q(:)=0 do p1=p,1,-1 if (mod(p,p1)/=0) cycle q(p1)=q(p1)+C(m*n/p1,n/p1) do p2=1,p1/2 if (mod(p1,p2)/=0) cycle q(p2)=q(p2)-q(p1) end do ff=ff + f(m-1,n,p1) * q(p1)*p1/p end do end if end function f integer(LONG) function C(n,k) implicit none integer(LONG):: n,k integer:: i C=1 do i=1,min(k,n-k) C=C*(n-i+1)/i end do end function C end program p281 Python: import fractions, math, operator, functools k = 10 ** 15 fact = [1] for i in range(1, 100): fact.append(i * fact[-1]) def choose(n, k): return fact[n] // fact[n - k] // fact[k] def tot(x): return sum(fractions.gcd(x, y) == 1 for y in range(1, x + 1)) def divs(x): for d in range(1, x + 1): if x % d == 0: yield d def f(m, n): return sum(tot(n // d) * functools.reduce(operator.mul, (choose(i * d, d) for i in range(2, m + 1)), 1) for d in divs(n)) // m // n c = 0 for n in range(1, 50): for m in range(2, 50): if f(m, n) > k: break else: c += f(m, n) print(c) Mathematica: g[m_, n_] := Multinomial @@ Array[n&, m] h[m_, n_] := (Total[g[m, #] MoebiusMu[n / #]& /@ Divisors[n]]) / (m n) f[m_, n_] := Total[h[m, #]& /@ Divisors[n]] L = 10^15; nMax[m_] := NestWhile[# + 1&, 1, f[m, #] <= L&] - 1 For[m = 2; ans=0, nMax[m]>0, m++, ans += Sum[f[m, n], {n, nMax[m]}]]; ans Java: import java.util.*; import java.math.*; public class P281 { static BigInteger[][] ways = new BigInteger[100][100]; static int gcd(int a, int b) { while (b!=0) { int t = a%b; a = b; b = t; } return a; } static BigInteger getit(int M, int N) { if (ways[M][N]!=null) return ways[M][N]; BigInteger ret = BigInteger.ONE; for (int i=1; i<=M*N; i++) ret = ret.multiply(new BigInteger(""+i)); for (int i=0; i<M; i++) for (int j=1; j<=N; j++) ret = ret.divide(new BigInteger(""+j)); return ways[M][N]=ret; } public static void main(String[] args) { BigInteger ret = BigInteger.ZERO; for (int M=2; ; M++) { boolean foundans = false; for (int N=1; ; N++) { BigInteger ans = BigInteger.ZERO; for (int i=1; i<=N; i++) { int g = gcd(i,N); ans=ans.add(getit(M,g)); } ans = ans.divide(new BigInteger(""+(M*N))); if (ans.compareTo(new BigInteger("1000000000000000"))>0) break;; foundans = true; ret = ret.add(ans); } if (!foundans) break; } System.out.println(ret); } }