106 - Fermat vs. Pythagoras

[bigredteam2000]

Eventhough it runs fine on the sample input I am getting a wrong answer.

//@begin_of_source_code
/*@JUDGE_ID: 15975FF 106 C++*/
#include<iostream.h>
#include<math.h>

int gcd( int a, int b)
{
int r;

do
{
r = a % b;
a = b;
b = r;
}while(r!=0);

return a;

}

int main()
{
long int N;
int t,s;
int n,m;
int i;
long int x,y;
long int z;
int count, count1;
bool B[1000001];


for( i = 0;i <=1000000; i++)
B = false;
while( cin>>N)
{
count = 0;
n=1;
t=n*n;
while(t < N)
{
m = n+1;
z = t+m*m;
while(z <= N)
{
x = m*m-n*n;
y = 2*m*n;
//cout << "found" << endl;
//cout<<x<<' '<<y<<' '<<z<< endl;
if(gcd (x,y) ==1)
{
if(gcd (y,z) ==1)
{
if(gcd (x,z) ==1)
{
//cout << "accept" << endl;
//cout<<x<<' '<<y<<' '<<z<< endl;
count ++;
B[x] = true;
B[y] = true;
B[z] = true;
i = 2;
s = i * z;
while(s <= N)
{
//cout << "eliminating" << endl;
//cout<<x*i<<' '<<y*i<<' '<<s<< endl;
B[s] = true;
B[i*x] = true;
B[i*y] = true;
i++;
s = i * z;
}
}
}
}
//cout <<x <<' '<<y<<' '<<z<<endl;
m++;
z = t+m*m;
}
n++;
t = n*n;
}
count1 = 0;
for( i = 1;i <=N; i++)
if(!B)
{
//cout << i <<' '<<i*i << endl;
count1++;
}

cout << count << ' ' << count1 << endl;;
//cout << "done"<<endl;
}
return 0;
}

//@end_of_source_code

[Pavel]

Hello,

while solving this problem I noticed that the quotient of N and the number of relatively prime triples is almost 2 * PI (6.2831853071...).
For example for N = 1000000 it's 1000000 / 159139 = 6.28381477, for N = 10000000 it's 10000000 / 1591579 = 6.28306857.

So I would like to ask if it's true that the quotient of N and the number of relatively prime triples goes to 2 * PI as N goes to inifinity. Can somebody prove or disprove it?

Pavel

[arnsfelt]

Try this:

http://mathworld.wolfram.com/PythagoreanTriple.html

[nidive]

You should put the for loop used to initialize the B array inside the while loop.

[incorrect]
for( i = 0;i <=1000000; i++)
B = false;
while( cin>>N)
{

[corrected]
while( cin>>N)
{
for( i = 1;i <=N; i++)
B = false;

[Archangel]

Can anybody help me why I always got Wrong answer on this problem?..thanks a lot!!

#include<stdio.h>
long count,upper_bound;
long list_count;
long m,n,x,y,z,o,temp_z;

long re_prime(long num1, long num2)
{
int r;
do
{
r = num1 % num2;
num1 = num2;
num2 = r;
} while (r != 0);
return num1;
}

main()
{
while(scanf("%d",&upper_bound) != EOF)
{
bool *ptr = new bool [upper_bound+1];
list_count = 0;
count = 0;
m = 1;
n = 1;
while(1)
{
m = n+1;
z = m*m + n*n;
if (z>upper_bound)
break;
while(z <= upper_bound)
{
x = m*m - n*n;
y = 2*m*n;
if (*(ptr+x) != true)
{
*(ptr+x) = true;
list_count++;
}
if (*(ptr+y) != true)
{
*(ptr+y) = true;
list_count++;
}
if (*(ptr+z) != true)
{
*(ptr+z) = true;
list_count++;
}
if((re_prime(x,y)==1)&&(re_prime(y,z)==1)&&(re_prime(z,x)==1))
{
count++;
o = 2;
temp_z = o*z;
while(temp_z<=upper_bound)
{
if(*(ptr+o*x) != true)
{
*(ptr+o*x) = true;
list_count++;
}
if(*(ptr+o*y) != true)
{
*(ptr+o*y) = true;
list_count++;
}
if(*(ptr+temp_z) != true)
{
*(ptr+temp_z) = true;
list_count++;
}
o++;
temp_z = o*z;
}
}
m++;
z = m*m + n*n;
}
n++;
}
printf("%d %d\n",count,upper_bound-list_count);
delete(ptr);
}
}

[tomy]

Maybe you should initialize your bool-array?

[Kamp]

You should check your program once again

For to sample input it gives strange (wrong) output !

Good Luck

[Archangel]

The problem has been solved~thanks!!

[bumpkin]

Can anybody explain us what is the second result asked in this problem (what do we have to count?). Thanks.

Alguien puede explicarnos exactamente que es el segundo valor que piden en este problema (que es lo que hay que contar). Gracias.
Los Bumpkins.[/cpp]

[10153EN]

The second number is asking how many number <= N is not part of the triples of the equation x^2 + y^2 = z^2.

Take the 1st sample input as example: 10
for x,y,z <= 10, there exists only 2 triples (not necessarily relatively prime), namely
3^2 + 4^2 = 5^2 and
6^2 + 8^2 = 10^2
for all positive integers <= 10, i.e. 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
the positive integers involves in the above triples are: 3, 4, 5, 6, 8, 10
=> the positive integers not involved in the triples are: 1, 2, 7, 9
=> the number of positive integers not involved in the triples is 4

Hope can help

[bumpkin]

Great, thanks. This should do it.

[selnip]

If Sample Input is 10

Sample output is 1 4 ?

wrong?

[tatter]

Currently I am working on problem 106 and using the following method:

x^2 = z^2 - y^2
x^2 = (z + y)(z - y)
let a = z + y
if x^2 is divisible by a,
x^2 = ab
where b is the other root
also since
(z + y) - (z - y) = 2y
(z + y) + (z - y) = 2z

therefore if
a + b is divisible by 2
then we can get z by (a + b)/2
and y by (a - b)/2

the problem with this is, i could not get pass N = 5000 without the program becoming significantly slow. from what i am doing, i need a loop for x, and another inner loop to find a. and since a can run from anything from 1 to x, both x and a are limited by N

so if N = 1 000 000, I will be doing N * N iterations which is too much for the program. Is there any other algo to solve the problem? or is there a way to remove the inner loop?

[tatter]

[cpp]#include <cstdio>
#include <iostream>
using namespace std;

#define MAX_NUMBER 1000000

unsigned int* v;

int gcd(int i, int j) {
while (i!=j)
if (i<j) j=j-i;
else i=i-j;
return i;
}

bool checkprime(unsigned int i,unsigned int j,unsigned int k) {
if (gcd(i, j) == 1)
if (gcd(i, k) == 1)
if (gcd(j, k) == 1)
return true;
return false;
}

int main() {
unsigned int a, b, c, d, m, numprime, nump, step, start;
while (cin >> m) {

nump = 0;
numprime = 0;
v = new(unsigned int[MAX_NUMBER+1]);

for (unsigned int i=3; i<=m; i++) {
a = (i*i);
if (i%2 == 0) {
start = 2;
step = 2;
} else {
start = 1;
step = 1;
}

for (unsigned int j=start; j<=i; j=j+step) {
if (a%j == 0)
b = a / j;
else continue;

c = b - j;
if (c>=2)
if (c%2 == 0) {
c /= 2;
d = (b + j) / 2;
if (c>i)
if (c<=m)
if (d<=m) {
if (!v) nump++;
if (!v[c]) nump++;
if (!v[d]) nump++;
if (checkprime(i,c,d)) {
if (i>=100) {
}
numprime++;
}
v = 1;
v[c] = 1;
v[d] = 1;
}
}

}
}

cout << numprime << " " << m - nump << endl;
delete[] v;
}

return 1;
}
[/cpp]

[tatter]

i was thinking...
what if i instead of iterating through all possible numbers from 0 to N, i generate a list of numbers to go through. this list of number would have all the multiples of the previously generated triples struck out as we know these are confirmed cases. that would have leave us a smaller list of number to go through

for e.g.
we have (3, 4, 5) initially, so we struck off (6, 8, 10), (9, 12, 15) ...

the question is, will i save time in doing this or is it that the time saved will be compensated by the fact that i still have to generate the list?

also, is that a better way to count the no. of numbers, p, that do not belong to any triple? other than using an array...

i was thinking of using a bit mask instead, to save space, but then again, it need 1 000 000 bits => 125 000 bytes, and the time needed to clear the bit mask each time a new data is entered is too wasteful

[Edited] oops, this should have occured to me earlier, should have used a linked list or something like that... [/Edited]