# My Weblog

## SPOJ 4186. Break a New RSA system

SPOJ 4186. Break a New RSA system is related to searching a root in given interval. We have
$n = p * q * r \hspace{ 20 pt} (1)$
$\phi_{n} = ( p - 1 ) * ( q - 1 ) * ( r - 1 ) \hspace{ 20 pt} (2)$
$\sigma_{ n }= ( p + 1 ) * ( q + 1 ) * ( r + 1 ) \hspace{ 20 pt} (3)$
$\frac {\phi_{n} + \sigma_{n}} {2} = p + q + r + n \hspace{ 20 pt} (4)$
Subtracting 2 and 3
$\frac {\sigma_{n} - \phi_{n} } {2} = qr + pr + pq + 1 \hspace{ 20 pt} (5)$
In 5 , we can replace $qr$ by $\frac {n} {p}$ and take p common from second and third so our final equation will be
$\frac {\sigma_{n} - \phi_{n} } {2} = \frac {n} {p} + p(r + q ) + 1 \hspace{ 20 pt} (6)$
From equation 4 , replacing the valuve $r + q$ in 6 we get a cubic equation in p . Our final equation will be
$2*p^3 + (2 * n - \phi_{n} - \sigma_{n})*p^2 + ( \sigma_{n} - \phi_{n} - 2 ) * p + (-2n) = 0 \hspace{ 20 pt} (7)$ .If we differentiate equation 7 and equate to 0 ,two roots of quadratic equation are either local minima and maxima or vice-verse of equation 7 and one of the root of equation 7 will be in this interval. We can search this root by binary search [ why ? because either the function will be increasing or decreasing in this interval ]. After getting one root , divide the equation 7 by this root [ see factorisation ] and get the other 2 roots of quadratic equation by closed form . The time limit for this problem is very tight so Haskell solution got time limit exceed while c++ passed. Accepted code

#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
typedef long long ll;

ll fuN( ll a , ll b , ll c , ll d , ll x )
{

return ( ( a * x + b ) * x + c ) * x + d ;
}

ll bsearch( ll a , ll b , ll c , ll d , ll lo , ll hi )
{
ll mid ;
while( lo < hi )
{
mid = ( lo + hi ) >> 1 ;
ll f = fuN ( a , b, c , d , lo );
ll s = fuN ( a , b, c, d , mid ) ;
if( ( f > 0 && s > 0 ) || ( f < 0 && s < 0) ) lo = mid + 1 ;
else hi = mid ;
}

return lo;
}

void solve ( ll n , ll phi , ll sigma )
{

ll a = 2 , b = 2 * n - phi - sigma , c = sigma -  phi - 2 , d = -2 * n ;
ll dis = ( ll ) sqrtl( ( 4 * b * b - 12 * a * c ) * 1.0 ) ;
ll low =( ll )  ceill( ( -2 * b - dis ) / ( 6.0 * a ) );
ll high = ( ll ) floor ( ( -2 * b + dis ) / ( 6.0 * a ) );
ll r = bsearch (  a , b , c , d ,  low , high ) ;
ll d1 = -( b + r * a );
ll d2 = ( ll ) sqrtl ( b * b  - 4 * a * c - 2 * a * b * r - 3 * a * a * r * r ) ;
ll r1 = ( ll ) ( ( d1 - d2 ) / ( 2 * a ) ) ;
ll r2 =  ( ll ) ( ( d1 + d2 ) / ( 2 * a ) ) ;
printf("%lld %lld %lld\n", r1 , r , r2 );

}

int main()
{

int t;
ll n , phi , sigma ;
for(scanf("%lld",&t ) ; t > 0 ; t--)
{
scanf("%lld %lld %lld", &n , &phi , &sigma );
solve ( n , phi , sigma );
}
}


import Data.List
import Data.Bits
import Data.Maybe
import qualified Data.ByteString.Char8 as BS

bSearch :: ( Num a , Integral a , Bits a ) => [ a ] -> a -> a -> a
bSearch [ a , b , c , d ] low high = helpBsearch low high where
helpBsearch lo hi
| lo >= hi = lo
| fuN lo * fuN mid > 0 = helpBsearch ( succ mid ) hi
| otherwise = helpBsearch lo mid
where mid = shiftR ( lo + hi )  1
fuN x = ( ( a * x + b ) * x + c ) * x + d

solve :: ( Num a , Integral  a , Bits a ) => [ a ] ->  BS.ByteString
solve [n , phi , sigma ] = roots    where
( a , b , c , d )  = ( 2 , 2 * n - phi - sigma ,  sigma - phi - 2 , -2 * n )
dis =   sqrt . fromIntegral $4 * b ^ 2 - 12 * a * c low =ceiling$ ( ( fromIntegral $-2 * b ) - dis ) / ( fromIntegral$  6 * a  )
high = ceiling $( ( fromIntegral$  -2 * b  )   +  dis  ) / ( fromIntegral $6 * a ) r = bSearch [ a , b , c , d ] low high d1 = -( b + r * a ) d2 = truncate.sqrt.fromIntegral$ b ^ 2 - 4 * a * c - 2 * a * b * r - 3 * a ^ 2 * r ^ 2
r1 = div ( d1 - d2 ) ( 2 * a )
r2 = div ( d1 + d2 ) ( 2 * a )
roots =  BS.append  ( BS.append ( BS.append ( BS.append ( BS.pack.show $r1 ) ( BS.pack " " ) ) ( BS.pack.show$ r ) ) ( BS.pack " " ) ) ( BS.pack.show $r2 ) readInt :: BS.ByteString -> Integer readInt = fst . fromJust . BS.readInteger main = BS.interact$ BS.unlines . map ( solve . map readInt . BS.words ) . tail . BS.lines