Euler Projesi 279. Soru

Kenar uzunlukları ve bir iç açısı tam sayı olan üçgenler

Kenar uzunlukları ve en az bir iç açısı (derece cinsinden) tam sayı olan ve çevre uzunluğu en fazla $10^8$ olan kaç üçgen bulunur?

Cevap:
416577688
C/C++: #include <stdio.h> #define N 100000000 long long int answer = 0; int main(int argc, char **argv) { int m, n; long long int len; //60, 120 answer += N/3; for (n=1;; n++) { for (m=n+1;; m++) { len = m+n; len *= 2*m+n; if (len > N) break; if ((m-n)%3==0) continue; if (calc_gcd(m,n)!=1) continue; answer += N/len; } if (m==n+1) break; } for (n=1;; n++) { for (m=n+1;; m++) { len = m+n; len *= 3; len *= m; if (len > N) break; if ((m-n)%3==0) continue; if (calc_gcd(m,n)!=1) continue; answer += N/len; } if (m==n+1) break; } for (n=1;; n++) { for (m=n+1;; m++) { len = 2*m+n; len *= m+2*n; if (len > N) break; if ((m-n)%3==0) continue; if (calc_gcd(m,n)!=1) continue; answer += N/len; } if (m==n+1) break; } //90 for (n=1;; n++) { for (m=n+1;; m++) { len = m+n; len *= 2; len *= m; if (len > N) break; if ((m-n)%2==0) continue; if (calc_gcd(m,n)!=1) continue; answer += N/len; } if (m==n+1) break; } printf ("answer: %lld\n", answer); } int calc_gcd(int a, int b) { int tmp; // change to "a>=b" if (a<b) { tmp = a; a = b; b = tmp; } while (b) { tmp = a%b; a = b; b = tmp; } return a; } Python: include "gcd.f90" program p279 use gcdLONG implicit none integer,parameter:: LONG=SELECTED_INT_KIND(16) integer(LONG):: cntr=0 integer(LONG):: p,q,r,a,b,c,b1,b2,u integer(LONG):: UMAX= 10**8 ! gamma=90 do p=2,UMAX if (2*p*p>=UMAX) exit do q=mod(p+1,2_LONG),p-1,2 if (gcd(p,q)/=1) cycle a=p*p-q*q b=2*p*q c=p*p+q*q u=a+b+c if (u>UMAX) exit cntr=cntr+UMAX/u end do end do ! equilateral triangles cntr = cntr + UMAX/3 ! gamma=60 or 120 do q=2,UMAX if (2*q*q>=UMAX) exit do r=1,q-1 c=q*q+q*r+r*r a=q*q+2*q*r if (a+c>=UMAX) exit b1=r*r+2*q*r b2=a-b1 if (gcd(gcd(a,c),b1)/=1) cycle ! gamma=120 (b1,b2,c) u=b1+b2+c cntr=cntr+UMAX/u ! gamma=60 (a,b1,c) u=a+b1+c cntr=cntr+UMAX/u ! gamma=60 (a,b2,c) u=a+b2+c cntr=cntr+UMAX/u end do end do write(*,*) cntr end program p279 Java: public class prob279{ public static boolean GCD(long a,long b){ while(a != 0 && b != 0){ if(a == 1 || b == 1) return true; else{ if(a > b) a = a%b; else b = b%a; } } return false; } public static void main(String arg[]){ long N = 100000000L; long total = 0L; //120 degrees for(long m = 1L; m <= 10000L; m++){ for(long n = 1L; n < m; n++){ if(!GCD(m,n) || (m-n)%3 == 0) continue; long temp = 3*m*n+2*m*m+n*n; if(temp > N) break; else total += N/temp; } } //60 degrees for(long m = 1L;m <= 10000L; m++){ for(long n = 1L; n <m; n++){ if(!GCD(m,n) || (m-n)%3 == 0) continue; long temp1 = 5*m*n+2*n*n+2*m*m; long temp2 = 3*m*n+3*m*m; if(temp1 > N && temp2 > N) break; else total += (N/temp1+N/temp2); } } total += N/3; //90 degrees for(long m = 1L; m <= 10000L; m++){ for(long n = 1L; n < m; n++){ if(!GCD(m,n) || (m-n)%2 == 0) continue; long temp = 2*m*(m+n); if(temp > N) break; else total += N/temp; } } System.out.println(total); } } ml: let m90 = [ 1, -2, 2, 2, -1, 2, 2, -2, 3; 1, 2, 2, 2, 1, 2, 2, 2, 3; -1, 2, 2, -2, 1, 2, -2, 2, 3 ] let m120 = [ -1, -4, 4, 1, -3, 4, 0, -6, 7; -1, 3, 4, 1, 4, 4, 0, 6, 7; 4, 3, 4, 3, 4, 4, 6, 6, 7; 4, 1, 4, 3, -1, 4, 6, 0, 7; -3, 1, 4, -4, -1, 4, -6, 0, 7 ] let t = 100000000 let rec trans flag acc a b c l = let t2 ac2 (m11, m12, m13, m21, m22, m23, m31, m32, m33) = trans flag ac2 (m11 * a + m12 * b + m13 * c) (m21 * a + m22 * b + m23 * c) (m31 * a + m32 * b + m33 * c) l in let k = t / (a + b + c) in if k = 0 then acc else let k = if flag then k + t / (a + a + b + c) + t / (a + b + b + c) else k in List.fold_left t2 (acc + k) l let main () = trans false 0 3 4 5 m90 + trans true 0 3 5 7 m120 + trans true 0 8 7 13 m120 + t / 3 ;; Printf.printf "%d\n" (main ()) Mathematica: p = 10^8; S = 0; (* b^2 = a^2 + c^2 - ac *) n = 1; While[(m = Range[n + 1, Min[3*n, (-3*n + Sqrt[9*n^2 + 8*p])/2]]) != {}, If[OddQ[n], m = Select[m, OddQ]; m = Select[ m, GCD[n, #] == 1 &], m = Select[m, EvenQ]; m = Select[m, GCD[n, #] == 2 &]]; For[i = 1, i <= Length[m], i++, a = (m[[i]]^2 + 2*m[[i]]*n - 3*n^2)/4; b = (m[[i]]^2 + 3*n^2)/4; c = m[[i]]*n; If[GCD[b, c] == 1, S = S + Floor[p/(a + b + c)]]]; n++] // Timing S n = 1; While[(m = Range[Floor[n/3 + 1], Min[n, (-3*n + Sqrt[3*(3*n^2 + 8*p)])/6]]) != {}, If[OddQ[n], m = Select[m, OddQ]; m = Select[m, GCD[n, #] == 1 &], m = Select[m, EvenQ]; m = Select[ m, GCD[n, #] == 2 &]]; For[i = 1, i <= Length[m], i++, a = (3*m[[i]]^2 + 2*m[[i]]*n - n^2)/4; b = (3*m[[i]]^2 + n^2)/4; c = m[[i]]*n; If[GCD[b, c] == 1, S = S + Floor[p/(a + b + c)]]]; n++] // Timing S (* a^2 + b^2 = c^2 *) n = 1; While[(m = Range[n + 1, Min[(1 + Sqrt[2])* n, (-n + Sqrt[n^2 + 2*p])/2]]) != {}, If[OddQ[n], m = Select[m, EvenQ], m = Select[m, OddQ]]; m = Select[m, GCD[n, #] == 1 &]; For[i = 1, i <= Length[m], i++, a = m[[ i]]^2 - n^2; b = 2*m[[i]]*n; c = m[[i]]^2 + n^2; S = S + Floor[p/(a + b + c)]]; n++] // Timing S n = 1; While[(m = Range[Ceiling[(1 + Sqrt[2])*n], (-n + Sqrt[n^2 + 2*p])/2]) != {}, If[OddQ[n], m = Select[m, EvenQ], m = Select[m, OddQ]]; m = Select[m, GCD[n, #] == 1 &]; For[i = 1, i <= Length[m], i++, a = 2*m[[i]]*n; b = m[[i]]^2 - n^2; c = m[[i]]^2 + n^2; S = S + Floor[p/(a + b + c)]]; n++] // Timing S (* c^2 = a^2 + b^2 + ab *) n = 4; While[(m = Range[Ceiling[(-3 + 2*Sqrt[3])*n], Min[n - 1, (2*p - 3* n^2)/n]]) != {}, If[OddQ[n], m = Select[m, OddQ]; m = Select[m, GCD[n, #] == 1 &], m = Select[m, EvenQ]; m = Select[m, GCD[ n, #] == 2 &]]; For[i = 1, i <= Length[m], i++, a = (3*n^2 - 2* m[[i]]*n - m[[i]]^2)/4; b = m[[i]]*n; c = (m[[i]]^2 + 3*n^2)/4; If[GCD[ b, c] == 1, S = S + Floor[p/(a + b + c)]]]; n++] // Timing S n = 4; While[(m = Range[Ceiling[(-3 + 2* Sqrt[3])/3*n], Min[Ceiling[n/3 - 1], (2*p - n^2)/n]]) != {}, If[OddQ[n], m = Select[m, OddQ]; m = Select[m, GCD[n, #] == 1 &], m = Select[m, EvenQ]; m = Select[m, GCD[ n, #] == 2 &]]; For[i = 1, i <= Length[m], i++, a = (n^2 - 2* m[[i]]*n - 3*m[[i]]^2)/4; b = m[[i]]*n; c = (3*m[[ i]]^2 + n^2)/4; If[GCD[b, c] == 1, S = S + Floor[p/(a + b + c)]]]; n++] // Timing S