# My Weblog

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

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

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


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

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

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) {
}
// System.out.println(res3);

} else {
res3 = res3.subtract(d);
if (res3.compareTo(BigInteger.ZERO) == -1) {