106 - Fermat vs. Pythagoras

[new_tim]

Hi tatter:

Can you please explain how your code works??
Thanks

[new_tim]

Hi tatter:
I think i understand how you can the root...
but in term of speed, this is still slower.
how can i make it within 10s??
thanks

[new_tim]

The time limit is now changed to 10s.
How can I make that??
In my mind, I have to use 2 loops, one for the x, and one for finding the root. If we can find the root, then y and z can be found.
However, the speed is extremely slow if N is 100000, since there are N*N iterations.
Please help...

[tatter]

the idea is to make the loop dependent on z instead of x or y
where x^2 + y^2 = z^2
since we know z>x and z>y, using this info we can be sure we can build our result based upon a previous result of z

let's do some calculations:

x^2 + y^2 = z^2

letting x = z - a, y = z - b

(z - a)^2 + (z - b)^2 = z^2
(z - (a + b))^2 = 2ab

letting v = a+b, w = ab,

(z - v)^2 = 2w
w = ((z - v)^2)/2

for simplicity of view, let t = z - v,

w = (t^2)/2

since we know that t = z - a - b, this means that t <= z
hence now we are dependent on z, instead of y from my previous code

note that w and t must be integers, this implies that t^2 must be even.
and since we know that the square of an odd number will be an odd number also, t must be even. So for N = 1 000 000, we cut the loop to half already.

next notice that for each even number of t, it will yield an answer (unlike my previous code where it will loop through doing all possible cases).

supposed that we have a solution t = i, yield w = j. now suppose we let
t = 2i, the equation becomes

w = 4(i^2)/2
= 4j

then since we had done t = i, we have the factors of w = j, so when t = 2i, the factors of w can be found from the factors when t = i, and 4.

Perhaps an example will be clearer,

for t = 2,
w = (2^2)/2
= 2
the factor are 1, 2

now when t = 4,
w = (4^4)/2
= 8
= 4 * 2
so the factor are 1, 2, 4, 8

look at it this way:

the factor of 4 the factor of 2
1 2 4 1 2

let us ignore 1s, so we have

the factor of 4 the factor of 2
2 4 2

permuting, we get:

2 x 2 = 4
4 x 2 = 8

the new term we get is 8, so the factors are 1, 2, 4, 8

hope this helps

[tatter]

funny, ur method seems so familiar to mine esp after u read my message for help...

anyway, no one replied to my post (all my own posts ), but i posted in my message one way to do it using dynamic programming, u may like to refer to it.

[Moni]

Hi!
I am pasting the problems sample input output here from the main problem. My problem is that I am not sure what will be the input and how the output is made. I know about Pythagorean triples i.e.

X^2 - Y^2, 2XY, X^2+Y^2

But how this is related with the problem? Anybody explain.

Given a positive integer N, you are to write a program that computes two quantities regarding the solution of

where x, y, and z are constrained to be positive integers less than or equal to N. You are to compute the number of triples (x,y,z) such that x<y< z, and they are relatively prime, i.e., have no common divisor larger than 1. You are also to compute the number of values such that p is not part of any triple (not just relatively prime triples).
The Input
The input consists of a sequence of positive integers, one per line. Each integer in the input file will be less than or equal to 1,000,000. Input is terminated by end-of-file.
The Output
For each integer N in the input file print two integers separated by a space. The first integer is the number of relatively prime triples (such that each component of the triple is ). The second number is the number of positive integers that are not part of any triple whose components are all . There should be one output line for each input line.

Sample Input
10
25
100

Sample Output
1 4
4 9
16 27

[Dominik Michniewski]

If I correct remember this Pythagorean triples generates all Pythagorean triangles, but It's possible to get in this way incorrect solution, i.e. this formula may generate 6,8,10 which is (3,4,5)*2 - this second triangle must be elimianted from counting!

You must compute in this problem to things:
- number of unique Pythagorean triangles, which starts the sequence of triangles (that means: (3,4,5) starts, but (4,6,8) not)
- amount of numbers, which not participate in any pythagorean triangle

Example (input case 1):
10
Output:
1 - it is one triangle which have all sides in correct range (3,4,5)
4 - from all ten numbers six participate in two triangles (3,4,5) and (6,8,10) - also solution is 10-6 = 4

exact algorithm is given to all other cases ...

Best regards
Dominik

[Moni]

Can you put few other sample inputs and outputs for test my prog ?

[PMNOX]

maybe we can use algorithm from problem 294 (dividors)?
my algorithm calculates all dividors from 1 to 1000000 in 35 s, maybe there is faster way to do it?

[PMNOX]

Archangel how did you discovered than for any m > n
and
x = m*m - n*n
y = 2*m*n
z = m*m + n*n

x,y,z will be all ways triple that:

x*x + y*y = z*z??
ofcourse it's true, it's easy to prove it

[Dominik Michniewski]

Maybe you can use this algorithm ....

But to this problem exist fast algorithm O(N^2) which generates all triangles, which we search (and a few more ... ) if I correct remember,
it's based on solving set of equations:
x = a*a + b*b
y = a*a - b*b
z = 2*a*b ....
a,b are iterators, x,y,z - sides of triangle

DOminik

[PMNOX]

ok thx

[prilmeie]

I am also getting WA on this problem. Maybe someone can help me?

I think I am having problems with the last for - Loop in the solve functions, because it once worked before the upper bound for the problem has been moved to 1000000.

Regards,
Franz

[cpp]#include <iostream>
#include <bitset>

const int N_MAX = 1000000;

inline bool relative_prime( long u, long v )
{
while ( v > 0 ) {
int r = u % v;
u = v;
v = r;
}

return ( u == 1 );
}

void solve( const int N )
{
static std::bitset<N_MAX> triples;
triples.reset();

for ( int j = 0; j <= N; ++j ) {
triples[ j ] = false;
}

int pair = 0;
int not_part = 0;

for ( int m = 2; m < N; ++m ) {
for ( int n = 1; n < m; ++n ) {
// m and n must not be both odd and must be relative prime

if ( (m % 2 == n % 2) || !relative_prime( m, n ) ) {
continue;
}

long z = m * m + n * n;
if ( z > N ) {
break;
}

long x = ( m + n ) * ( m - n );
if ( x > N ) {
break;
}

long y = 2 * n * m;
if ( y > N ) {
break;
}

// all relative prime triple are of the form
// ( m^2 - n^2, 2 * m * n, m^2 + n^2 )

++pair;

// Now count all numbers which are part
// of a triple (either relative prime or not):
for ( long d = 1; d * z <= N && d * z > 0 && d * x > 0 && d * x <= N && d * y > 0 && d * y <= N;
++d ) {
if ( !triples.test( d * x - 1 ) ) {
triples.set( d * x - 1 );
++not_part;
}

if ( !triples.test( d * y - 1 ) ) {
triples.set( d * y - 1 );
++not_part;
}

if ( !triples.test( d * z - 1 ) ) {
triples.set( d * z - 1 );
++not_part;
}
}
}
}

std::cout << pair << ' ' << ( N - not_part ) << std::endl;
}

int main()

{
int N;

while ( true ) {
std::cin >> N;

if ( std::cin.eof() ) {
break;
}

solve( N );
}

return 0;
}[/cpp][/java]

[R]

@pril:
i think you should test x,y,z for an overflow when you set them, not in the for-loop that's too late - the pair count is already false then.
when z=-214987298734, that is definitely smaller than N

anyways:
i'm currently working on 106 using basically the same algorithm and still get WA

may someone, who has already solved the thing correctly, provide me with some extra correct input/output-data. the given examples are computed correctly by my program...
maybe i just missed a "+1" somewhere?

[R]

omg, i got it accepted

can't remember that i ever had to deal with multiple overflows. the problem should be dealt with, when there is a programming language with a longlonglonglonglonglonglonglong datatype