Kenar uzunlukları tamsayı olan ve $a\le b\le c$ eşitsizliğini sağlayan bir üçgenin kenarları, eğer $$a^2+b^2=c^2+1$$ eşitliğini sağlıyorsa bu üçgene hemen hemen dar açılı üçgen adı verilir.
Çevresi $\le 25000000$ olan kaç tane hemen hemen dar açılı üçgen vardır?
Cevap: 61614848
Delphi:
procedure TForm1.Button8Click(Sender: TObject);
const limit=25000000;
type triple=record
a,b,c:integer;
end;
var stack:array of triple;
n:triple;a,b,c,count,stacktop:integer;
maxsize:integer;
start,stop,freq:int64;
procedure push(a,b,c:integer);
var n:triple;
begin
n.a:=a;n.b:=b;n.c:=c;
inc(stacktop);
if stacktop>high(stack) then setlength(stack,stacktop+10000);
stack[stacktop]:=n;
end;
function pop:triple;
begin
result:=stack[stacktop];
dec(stacktop);
end;
begin
queryperformancecounter(start);
queryperformancefrequency(freq);
stacktop:=-1;
push(1,2,2);
push(1,1,1);
count:=0;
while stacktop>=0 do
begin
inc(count);
n:=pop;
a:=n.a;b:=n.b;c:=n.c;
if (a<b) and (7*c+5*b-5*a<=limit) then push(2*c + b - 2*a, 2*c + 2*b - a, 3*c + 2*b - 2*a);
if (7*c+5*b+5*a<=limit)then push(2*c + b + 2*a, 2*c + 2*b + a, 3*c + 2*b + 2*a);
if (7*c-5*b+5*a<=limit) then push(2*c - 2*b + a, 2*c - b + 2*a, 3*c - 2*b + 2*a);
end;
queryperformancecounter(stop);
memo1.lines.add(inttostr(count));
memo1.lines.add(floattostr((stop-start)/freq*1000));
end;Pascal:
program roxor;
uses minimaple;
type tri=array[1..3] of longint;
var t1,t2: array[1..50000000] of tri;
taille1,taille2:longint;
function compte(max:longint):longint;
var i,a,b,c,lim,som:longint;
begin
som:=2;
taille1:=2;
taille2:=0;
t1[1][1]:=1;
t1[1][2]:=1;
t1[1][3]:=1;
t1[2][1]:=2;
t1[2][2]:=1;
t1[2][3]:=2;
while taille1<>0 do
begin
lim:=taille1;
taille1:=0;
for i:=1 to lim do
begin
a:=t1[i][1];
b:=t1[i][2];
c:=t1[i][3];
if a-2*b+2*c+2*a-b+2*c+2*a-2*b+3*c<=max then
begin
taille2:=taille2+1;
t2[taille2][1]:=a-2*b+2*c;
t2[taille2][2]:=2*a-b+2*c;
t2[taille2][3]:=2*a-2*b+3*c;
som:=som+1;
end;
if a+2*b+2*c+2*a+b+2*c+2*a+2*b+3*c<= max then
begin
taille2:=taille2+1;
t2[taille2][1]:=a+2*b+2*c;
t2[taille2][2]:=2*a+b+2*c;
t2[taille2][3]:=2*a+2*b+3*c;
som:=som+1;
end;
if a<>b then
if -a+2*b+2*c-2*a+b+2*c-2*a+2*b+3*c<=max then
begin
taille2:=taille2+1;
t2[taille2][1]:=-a+2*b+2*c;
t2[taille2][2]:=-2*a+b+2*c;
t2[taille2][3]:=-2*a+2*b+3*c;
som:=som+1;
end;
end;
lim:=taille2;
taille2:=0;
for i:=1 to lim do
begin
a:=t2[i][1];
b:=t2[i][2];
c:=t2[i][3];
if a-2*b+2*c+2*a-b+2*c+2*a-2*b+3*c<=max then
begin
taille1:=taille1+1;
t1[taille1][1]:=a-2*b+2*c;
t1[taille1][2]:=2*a-b+2*c;
t1[taille1][3]:=2*a-2*b+3*c;
som:=som+1;
end;
if a+2*b+2*c+2*a+b+2*c+2*a+2*b+3*c<= max then
begin
taille1:=taille1+1;
t1[taille1][1]:=a+2*b+2*c;
t1[taille1][2]:=2*a+b+2*c;
t1[taille1][3]:=2*a+2*b+3*c;
som:=som+1;
end;
if a<>b then
if -a+2*b+2*c-2*a+b+2*c-2*a+2*b+3*c<=max then
begin
taille1:=taille1+1;
t1[taille1][1]:=-a+2*b+2*c;
t1[taille1][2]:=-2*a+b+2*c;
t1[taille1][3]:=-2*a+2*b+3*c;
som:=som+1;
end;
end;
end;
compte:=som;
end;
begin
writeln(compte(25000000));
end.C++:
#include "stijn.cpp"
typedef long long ui;
const int N = 25000000;
const int M = N / 4 + 1;
bool f[M];
vector<int> p,p_x,q,q_x,r,r_x;
void prime_factorisation(int i);
void combine();
ui a,b,c;
ui w,wk;
ui S;
// bepaalt vanuit priemfactorisatie r alle divisors van een getal
void all_divisors(ui &div, int &i) {
if( i == r.size() ) {
// we hebben unieke divisor te pakken
wk = w / div;
if( wk <= div ) return;
a = wk - div;
c = a + 2*div;
if( a + b + c <= N && (a <= b || a%2 == 0) ) S++;
return;
}
ui tmp = div;
int tmp_i = i + 1;
for(int j = 0; j <= r_x[i]; j++) {
all_divisors( tmp , tmp_i );
tmp *= r[i];
}
}
int main() {
double time = clock();
S = 1 + (N-1) / 4;
sieve(f,M);
cout << "Sieve klaar" << " in " << clock() - time << "ms" << endl;
p.clear();
p_x.clear();
int percent = 1;
for(int m = 2; m < M; m++) {
b = 2*m - 1;
w = (ui)m * (ui)(m - 1);
q = p; q_x = p_x;
prime_factorisation(m);
combine();
ui tmp = 1;
int tmp_i = 0;
all_divisors(tmp,tmp_i);
if ( 100 * m > percent*M ) {
cout << percent << "% : " << S << " in " << clock() - time << "ms" << endl;
percent++;
}
}
einde(S);
}
void prime_factorisation(int i) {
p.clear();
p_x.clear();
for(int j=2;i>1;j++) {
if( f[j] ) {
if( i%j == 0 ) {
i/=j; p.push_back(j); p_x.push_back(1);
while( i%j == 0 ) {i = i/j; p_x.back()++;}
}
if( f[i] ) {p.push_back(i); p_x.push_back(1); return;}
}
}
}
void combine() {
r.clear();
r_x.clear();
int p_i = 0, q_i = 0;
while( p_i < p.size() && q_i < q.size() ) {
if( p[p_i] < q[q_i] ) {
r.push_back( p[p_i] );
r_x.push_back( p_x[p_i] );
p_i++;
}
else if( p[p_i] > q[q_i] ) {
r.push_back( q[q_i] );
r_x.push_back( q_x[q_i] );
q_i++;
}
else {
r.push_back( p[p_i] );
r_x.push_back( p_x[p_i] + q_x[q_i] );
p_i++; q_i++;
}
}
while( p_i < p.size() ) {
r.push_back( p[p_i] );
r_x.push_back( p_x[p_i] );
p_i++;
}
while( q_i < q.size() ) {
r.push_back( q[q_i] );
r_x.push_back( q_x[q_i] );
q_i++;
}
}Python:
nmax = 25 * 10 ** 6
m = [[[-2, 1, 2], [-1, 2, 2], [-2, 2, 3]],
[[2, 1, 2], [1, 2, 2], [2, 2, 3]],
[[1, -2, 2], [2, -1, 2], [2, -2, 3]]]
s = [[1, 1, 1], [1, 2, 2]]
c = 0
while True:
t = []
c += len(s)
for a in s:
for mm in m if a[0] < a[1] else m[1:]:
b = [sum(mm[i][j] * a[j] for j in range(3)) for i in range(3)]
if sum(b) <= nmax:
t.append(b)
if not t:
break
s = t
print(c)Maple:
> N:=(a,b,c)->[[a-2*b+2*c,2*a-b+2*c,2*a-2*b+3*c],[a+2*b+2*c,2*a+b+2*c,2*a+2*b+3*c],[-a+2*b+2*c,-2*a+b+2*c,-2*a+2*b+3*c]]:
> N2:=(a,b,c)->[[a+2*b+2*c,2*a+b+2*c,2*a+2*b+3*c],[-a+2*b+2*c,-2*a+b+2*c,-2*a+2*b+3*c]]:
>
> HowMany:=proc(a,b,c)
> if a+b+c>25000000 then return 0 fi;
> if a=b or a=1 then return 1+add(HowMany(i[]),i in N2(a,b,c)) fi;
> return 1+add(HowMany(i[]),i in N(a,b,c))
> end:
>
> t:=time(): add(HowMany(1,a,a),a=2..12500000)+HowMany(5,5,7)+1; time()-t;
61614848
687.236