LL product_mod(LL a, LL b, LL mod)
{
    a %= mod;
    b %= mod;

    LL result = 0, y = a;

    while(b)
    {
        if(b&1)
            result = ((result%mod) + y) %mod;

        y = (y + y)%mod;

        b = b >> 1;
    }

    return result%mod;
}

This is also known as the Russian peasant method for multiplication.

For example, 7x13

13 = (8 + 4 + 1)

The product is re-written as 8.7 + 4.7. 1.7

In my code, y keeps track of 7, 2.7. 4.7, 8.7, etc.
It gets added to result whenever a bit is set in b.

Thanks! Luckily I have known about knoledge about quickpow. Very helpful segguestion!XD

Thank you again. I think I gain a lot after solving this question! I nearly knew nothing about matrix in the past.

Why the answer is 191? As far as I understand, we need to count numbers from 1000 to 1234 without 00. There are only 12 of them:
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1100
1200
So 1234 - 1000 - 12 = 222. Where am I wrong? Thanks.

теперь понятно. спасибо.

Edited by author 16.08.2010 12:46

// 1012.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
#include <deque>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
using namespace std;
const int SZ = 1000;

class verylong
{
private:
deque<char>vlstr;
int vlen;
verylong multdigit(const int) const;
verylong mult10(const verylong) const;
public:
verylong() : vlen(0)
{ vlstr[0]='\0'; }
verylong(const char s[SZ])
{ strcpy(vlstr, s); vlen=strlen(s); }
verylong(const unsigned long n)
{
sprintf(vlstr, "%lu", n);
_strrev(vlstr);
vlen=strlen(vlstr);
}
void putvl() const;
void getvl();
verylong operator + (const verylong);
verylong operator * (const verylong);
verylong operator - (const verylong);
};
//--------------------------------------------------------------

void verylong::putvl() const
{
char temp[SZ];
strcpy(temp,vlstr);
cout << _strrev(temp);
}
//--------------------------------------------------------------
void verylong::getvl()
{
cin >> vlstr;
vlen = strlen(vlstr);
_strrev(vlstr);
}
//--------------------------------------------------------------
verylong verylong::operator + (const verylong v)
{
char temp[SZ];
int j;

int maxlen = (vlen > v.vlen) ? vlen : v.vlen;
int carry = 0;
for(j = 0; j<maxlen; j++)
{
int d1 = (j > vlen-1)   ? 0 : vlstr[j]-'0';
int d2 = (j > v.vlen-1) ? 0 : v.vlstr[j]-'0';
int digitsum = d1 + d2 + carry;
if( digitsum >= 10 )
{ digitsum -= 10; carry=1; }
else
carry = 0;
temp[j] = digitsum+'0';
}
if(carry==1)
temp[j++] = '1';
temp[j] = '\0';
return verylong(temp);
}
//--------------------------------------------------------------
verylong verylong::operator - (const verylong v)
{
char temp[SZ];
    int j, p=0, r=0;

    int maxlen = (vlen > v.vlen) ? vlen : v.vlen;
    p = maxlen - 1;
    int carry = 0;

    for(j=0; j<maxlen; j++)
    {
        int d1 = (j > vlen-1) ? 0 : vlstr[j] - '0';
        int d2 = (j > v.vlen - 1) ? 0 : v.vlstr[j] - '0';
        int digitdif = d1 - d2 - carry;
        if(digitdif < 0)
        { digitdif += 10;  carry = 1; }
        else carry = 0;
        temp[j] = digitdif + '0';
    }
    temp[j] = '\0';

    return verylong(temp);
}
//--------------------------------------------------------------
verylong verylong::operator * (const verylong v)
{
verylong pprod;
verylong tempsum;
for(int j=0; j<v.vlen; j++)
{
int digit = v.vlstr[j]-'0';
pprod = multdigit(digit);
for(int k=0; k<j; k++)
pprod = mult10(pprod);
tempsum = tempsum + pprod;
}
return tempsum;
}
//--------------------------------------------------------------
verylong verylong::mult10(const verylong v) const
{
char temp[SZ];
for(int j=v.vlen-1; j>=0; j--)
temp[j+1] = v.vlstr[j];
temp[0] = '0';
temp[v.vlen+1] = '\0';
return verylong(temp);
}
//--------------------------------------------------------------
verylong verylong::multdigit(const int d2) const
{
char temp[SZ];
int j, carry = 0;
for(j = 0; j<vlen; j++)
{
int d1 = vlstr[j]-'0';
int digitprod = d1 * d2;
digitprod += carry;
if( digitprod >= 10 )
{
carry = digitprod/10;
digitprod -= carry*10;
}
else
carry = 0;
temp[j] = digitprod+'0';
}
if(carry != 0)
temp[j++] = carry+'0';
temp[j] = '\0';
return verylong(temp);
}


int main()
{
    verylong a[180], s[180];
    unsigned long n, i, k;
    scanf("%d", &n);
    scanf("%d", &k);

    a[0] = (n-n);
    s[0] = (k-1);


    for(i=1; i<n; i++)
    {
        s[i] = (verylong)k * s[i-1];
        s[i] = s[i] - a[i-1];
        a[i] = s[i-1] - a[i-1];
    }

    s[n-1].putvl();
    return 0;
}

My int main algo is right or not?


I wrote it in VC 2010.
You must wipe out #include "stdafx.h"
and main function must be int main()

Edited by author 19.08.2010 14:10