×

# Spoj problem AGS

 0 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=(value1ratio)%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.. asked 15 Mar '15, 22:09 4★sayaksan 26●1●4 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×1,138
×690
×1

question asked: 15 Mar '15, 22:09

question was seen: 814 times

last updated: 15 Mar '15, 22:09