My Weblog

Blog about programming and math

SPOJ Aritho-geometric Series (AGS)

AGS is rather simple problem. Write down couple of terms
a , a + d ,  ar + dr , ar + dr + d , ar^2 + dr^2 + dr . You can see
1. n is even
a*r^{\frac{n-1}{2}} + d*( 1 + r + r^2 \cdots + r^{\frac{n-1}{2}})
2. n is odd
a*r^{\frac{n-1}{2}} + d*( 1 + r + r^2 \cdots + r^{\frac{n-1}{2}}) - d
Accepted Haskell code.

import qualified Data.ByteString.Lazy.Char8 as BS

powM :: Integer -> Integer -> Integer -> Integer
powM a n m   -- a^n mod m
  | n == 0 = 1
  | n == 1 = mod a m
  | even n = ret
  | otherwise = mod ( a * ret ) m
  where
     ret = mod ( powM ( mod ( a ^ 2 ) m ) ( div n 2 ) m ) m

geoSum :: Integer -> Integer -> Integer -> Integer
geoSum r n m
  | n == 0 = mod 1 m
  | n == 1 = mod ( 1 + r ) m
  | odd n = mod ( ( 1 + powM r ( div ( n + 1 ) 2 ) m ) * mod ( geoSum r ( div ( n - 1 ) 2 ) m ) m ) m
  | otherwise = mod (  ( 1 + powM r ( div n 2 ) m ) * mod ( geoSum r ( div ( n - 1 ) 2 ) m ) m  +  powM r n m ) m

solve :: [ Integer ] -> [ BS.ByteString ]
solve [] = []
solve ( a : d : r : n : m : xs )
   | even n = ( BS.pack . show  $ ret )  :  solve xs
   | otherwise = (  BS.pack . show $ ( mod ( ret - d + m ) m ) ) :  solve xs
   where ret  =  mod ( mod ( a * powM r ( div ( n - 1 ) 2 ) m ) m  + mod ( d * geoSum r ( div ( n - 1 ) 2 ) m ) m ) m

readD :: BS.ByteString -> Integer
readD = fst . fromJust. BS.readInteger


main =  BS.interact $   BS.unlines . solve . map readD . concat . map BS.words . tail . BS.lines
Advertisements

December 12, 2012 - Posted by | Haskell, Programming | , ,

6 Comments »

  1. Struggling with its C++ implementation.. Pls help

    Comment by F777 | May 10, 2013 | Reply

  2. any help with its c++ implimentation

    Comment by raj kumar | September 17, 2013 | Reply

    • Hello Raj,
      Now I am not much into C/C++ programming so can’t help you with implementation.

      Comment by tiwari_mukesh | September 18, 2013 | Reply

      • sir plz explain your geosum function??

        Comment by raj kumar | September 18, 2013

  3. sir can u explain how you are calculating gp_sum using geosum function ???? i m not gettin how the geosum function is working

    Comment by raj kumar | September 18, 2013 | Reply

  4. hii…… i have implemented in java.. my code is running for almost 5 test cases in spoj and then it shows NZEC runtime error.. i am unable to find that plz could u see where that error comes from .. my code is below..

    import java.math.BigInteger;
    import java.util.Scanner;

    public class Main {

    public static void main(String[] args) {
    // TODO Auto-generated method stub

    Scanner sc = new Scanner(System.in);
    int t = sc.nextInt();

    BigInteger a, d, r, mod;
    int n;
    BigInteger res1, res2, res3;

    while (t– > 0) {
    a = sc.nextBigInteger();
    d = sc.nextBigInteger();
    r = sc.nextBigInteger();
    n = sc.nextInt();
    mod = sc.nextBigInteger();

    res1 = r.pow((n – 1) / 2).mod(mod);
    res2 = r.multiply(d).divide(r.subtract(BigInteger.valueOf(1)));

    res2 = (res2.add(a)).mod(mod);

    res3 = res1.multiply(res2).mod(mod);

    res3 = res3.subtract(d.divide(r.subtract(BigInteger.ONE)));

    if (n % 2 == 0) {
    if (res3.compareTo(BigInteger.ZERO) == -1) {
    res3 = (res3.add(mod)).mod(mod);
    }
    // System.out.println(res3);

    } else {
    res3 = res3.subtract(d);
    if (res3.compareTo(BigInteger.ZERO) == -1) {
    res3 = (res3.add(mod)).mod(mod);
    }
    }
    System.out.println(res3);
    }

    }
    }

    Comment by ajayv | May 20, 2014 | Reply


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: