## 106 - Fermat vs. Pythagoras

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

bigredteam2000
New poster
Posts: 11
Joined: Sat Nov 17, 2001 2:00 am
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;

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
New poster
Posts: 2
Joined: Tue Feb 05, 2002 2:00 am
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
New poster
Posts: 44
Joined: Wed Oct 17, 2001 2:00 am
Location: Denmark
Contact:

nidive
New poster
Posts: 1
Joined: Sun Apr 28, 2002 3:32 pm
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
New poster
Posts: 29
Joined: Wed Jun 26, 2002 9:00 am

### WA on problem 106 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
New poster
Posts: 2
Joined: Thu Jun 20, 2002 5:53 pm
Maybe you should initialize your bool-array?

Kamp
New poster
Posts: 18
Joined: Tue Mar 05, 2002 2:00 am
Location: Poland (3-city)
Contact:
You should check your program once again For to sample input it gives strange (wrong) output ! Good Luck Archangel
New poster
Posts: 29
Joined: Wed Jun 26, 2002 9:00 am

### Thanks for all of you pay attention for my problem!!

The problem has been solved~thanks!! bumpkin
New poster
Posts: 2
Joined: Thu Jul 04, 2002 9:20 pm

### Prob 106 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
Experienced poster
Posts: 148
Joined: Sun Jan 06, 2002 2:00 am
Location: Hong Kong
Contact:
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
New poster
Posts: 2
Joined: Thu Jul 04, 2002 9:20 pm
Great, thanks. This should do it. selnip
New poster
Posts: 2
Joined: Wed May 22, 2002 3:43 pm
Location: South of Korea

### Is it right?

If Sample Input is 10

Sample output is 1 4 ?

wrong?

tatter
New poster
Posts: 5
Joined: Mon Sep 30, 2002 9:43 am

### 106 : How to make it faster?

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
New poster
Posts: 5
Joined: Mon Sep 30, 2002 9:43 am

### The code

[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
New poster
Posts: 5
Joined: Mon Sep 30, 2002 9:43 am

### idea?

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]