Spoj problem AGS

ags
problem
spoj

#1

How to solve the spoj problem AGS? What is the fastest way to calculate (1+r+r^2+…r^n)mod M? I did not try modular inverse.Instead I tried something like the following:
(1+r)+r^2(1+r)+r^4(1+r)…
int findsum(int base,int exp,int mod)
{
/if exp is even then we can imagine exp as 2m/
/1+r+r^2+…+r^2m=1+r(1+r)+r^3*(1+r)+…+r^(2m-1)(1+r)/
if(exp%2==0)
{
int m=exp/2;
ll value1=base;
value1=value1%mod;
ll value2=(1+base);
value2=value2%mod;
ll ratio=base;//ratio=r^2 or base^2//posssiblee overflow if ratio is not long long
ratio*=base;
ratio=ratio%mod;
ll result=0;
for(int i=1;i<=m;i++)
{
result=((result%mod)+(value1value2)%mod)%mod;
value1=(value1
ratio)%mod;
}
result=(result+1)%mod;
return (int)result;
}
/if exp is odd then we can imagine exp as 2m-1
1+r+r^2+…r^2m-1=(1+r)+r^2(1+r)+…+r^(2m-2)(1+2)
/
else
{
//2m-1=exp or m=(exp+1)/2
int m=(exp+1)/2;
ll value1=base;
value1=value1%mod;
ll value2=(1+base);
value2=value2%mod;
ll ratio=base;//ratio=r^2 or base^2//posssiblee overflow if ratio is not long long
ratio*=base;
ratio=ratio%mod;
ll result=0;
for(int i=1;i<=m;i++)
{
result=((result%mod)+(value1value2)%mod)%mod;
value1=(value1
ratio)%mod;
}
result=(result)%mod;
return (int)result;
}
}
This is the implementation part of it. Please help me…