Gaussian Prime Integer Problem
Theory:
First we should know that the multiple of two lengths is the length of the original one. For example, (4,3) has a length of 5, so if we can break (4,3) down into A & B, length(A) * length(B) is also 5.
Next we’ll iterate through all possible combinations (lengths.) We’ll try length up to sqrt(5) in the above example because we can always find a factor whose length is less than or equal to that.
Last, just iterate through all combinations lead to that length and see if it works. To check that, you may just divide it. The code is the final formula for it.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
#include<cstdio> #include<cmath> bool gauss_prime( int R, int I ) { int len = R*R + I*I; double lim = sqrt( len ) + 1e-14; for( int a = 1; a <= lim; ++a ) for( int b = -lim; b <= lim; ++b ) if( a*a + b*b > 1 && a*a + b*b < len && ( R*R + I*I ) % ( a*a + b*b ) == 0 )//&& ( a*I - b*R ) % ( a*a + b*b ) == 0 return false; return true; } int main() { int t, r, i; scanf( "%d", &t ); while( t-- ) { scanf( "%d %d", &r, &i ); if( r < 0 && i < 0 ) r = -r, i = -i; printf( gauss_prime( r, i )? "P\n" : "C\n" ); } return 0; } |