You are not logged in. Please login at www.codechef.com to post your questions!

×

Spoj problem AGS

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

sayaksan's gravatar image

4★sayaksan
2614
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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