Hi Codeforces,

For a particular problem , i used first the predefined pow() function and then my own version of pow() function , named power().

Code :

#include<bits/stdc++.h>

using namespace std;

#define ull unsigned long long

ull power(ull a,ull n)
{

    ull res=1;

    while(n>=1)
    {

        if(n&1)  res*=a;

        n>>=1;

        a*=a;

    }

    return res;

}

int main()
{

    ull a=3,b=35;

    cout<<(ull)pow(a,b)-1<<" ";
    cout<<power(a,b)-1<<endl;

    return 0;

}

But , two of them give different outputs for same input.

The output on codeblocks is :

50031545098999705 50031545098999706

What can be reason for the same?

Hi all, i have been trying to solve this problem: http://www.spoj.com/problems/FIBOSQRT/

It is given that

1)F(n)=F(n-1)+F(n-2) with F(0)=0 and F(1)=1

2)Fs(n)=Fs(n-1)+Fs(n-2)+2*SQRT(3+Fs(n-1)*Fs(n-2)) with Fs(0) and Fs(1) are given in the input file.

What i am doing is : Let K(n) = sqrt(3 + F(n-1) F(n-2)). Then, after applying some mathematics , we get K(n) = F(n-2) + K(n-1). I got the idea from : http://www.quora.com/How-can-the-problem-FIBOSQRT-of-SPOJ-be-solved

After that, i tried to find the the matrix for the recurrence relation which i got as: matrix [3][3]={{1,1,0},{2,1,1},{0,1,0}};

After multiplying it for (n-1) times, i multiplied it by {K(2),f[1],f[0]} and calculated the result.

Here is my code: http://ideone.com/4ho8nX

I am getting correct answer for most of the cases but getting wrong answer everytime. It would be very helpful if anyone provides even slight help/correction.

Hi all,

While searching about inverse modulo, i got to know about a concise algorithm to find inverse modulo of numbers in range[1...n) under modulo m.

Time complexity of this approach is O(n).

Implementation of the algorithm:

r[1] = 1; for (int i=2; i<n; ++i) r[i] = (m — (m/i) * r[m%i] % m) % m;

Here is the link: http://e-maxx.ru/algo/reverse_element

I am unable to understand the proof of the algorithm. It would be very helpful if anyone explains the same in a simple way.