## 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

Adding 2 and 3

Subtracting 2 and 3

In 5 , we can replace by and take p common from second and third so our final equation will be

From equation 4 , replacing the valuve in 6 we get a cubic equation in p . Our final equation will be

.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 ); } }

Haskell code which got time limit exceed. If your Haskell solution is accepted then please let me know.

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

No comments yet.

## Leave a Reply