Sunday, August 28, 2016

uri- 1033 - How Many Calls?

#include <bits/stdc++.h>
using namespace std;
typedef long long Nu;

int bigmod(Nu n, const int M)
{
    if ( n <= 0 ) return 0;

    Nu a, b, c, d, r;
    a = 1, b = 0 , c = 0, d = 1;
    --n;

    while ( n > 0 )
    {
        if ( n&1 )
        {
            r = ( (d*b) + (c*a) )%M;
            b = ( d*(b+a) + (c*b) )%M;
            a = r;
        }

        r = ( c*c + d*d )%M;
        d = ( d * (2*c + d) )%M;
        c = r;

        n = n/2;
    }
    return (a + b)%M;
}

int main()
{
    Nu k;
    int g, h, re = 0;

    while (cin >> k >> g && (k || g) )
    {
        h = ( (2 * bigmod(k+1, g)) - 1 + g ) % g;
        printf("Case %d: %lld %d %d\n", ++re, k, g, h);
    }
    return 0;
}

No comments: