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

Post Reply
bigredteam2000
New poster
Posts: 11
Joined: Sat Nov 17, 2001 2:00 am

Post by bigredteam2000 » Wed Dec 26, 2001 8:24 pm

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
New poster
Posts: 2
Joined: Tue Feb 05, 2002 2:00 am

Post by Pavel » Wed Feb 13, 2002 4:11 pm

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:

Post by arnsfelt » Thu Feb 14, 2002 1:50 pm


nidive
New poster
Posts: 1
Joined: Sun Apr 28, 2002 3:32 pm

Post by nidive » Sun Apr 28, 2002 3:35 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

Post by Archangel » Wed Jun 26, 2002 9:16 am

:cry: 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

Post by tomy » Thu Jun 27, 2002 10:52 am

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:

Post by Kamp » Thu Jun 27, 2002 12:10 pm

You should check your program once again :)

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

Good Luck :D

Archangel
New poster
Posts: 29
Joined: Wed Jun 26, 2002 9:00 am

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

Post by Archangel » Thu Jun 27, 2002 1:14 pm

The problem has been solved~thanks!! :lol:

bumpkin
New poster
Posts: 2
Joined: Thu Jul 04, 2002 9:20 pm

Prob 106

Post by bumpkin » Thu Jul 04, 2002 9:25 pm

:evil:
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:

Post by 10153EN » Thu Jul 04, 2002 9:35 pm

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

Post by bumpkin » Fri Jul 05, 2002 5:07 pm

Great, thanks. This should do it. :D

selnip
New poster
Posts: 2
Joined: Wed May 22, 2002 3:43 pm
Location: South of Korea

Is it right?

Post by selnip » Tue Jul 16, 2002 1:09 pm

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?

Post by tatter » Mon Sep 30, 2002 9:52 am

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

Post by tatter » Mon Sep 30, 2002 10:16 am

[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?

Post by tatter » Mon Sep 30, 2002 11:35 am

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]

Post Reply

Return to “Volume 1 (100-199)”