CodeForces Beta Round #17 D. Notepad

Pythonゲーｷﾀ━━━(ﾟ∀ﾟ)━( ﾟ∀)━( 　ﾟ)━(　　)━(　　)━(ﾟ 　)━(∀ﾟ )━(ﾟ∀ﾟ)━━━!!!!!

b,n,c = [int(x) for x in raw_input().split()]
print ((b-1)*pow(b,n-1,c)+c-1)%c+1

→Time limit exceeded　orz

２行目は問題無いのだけど、１行目の読み込みに時間がかかる。10進数のまま冪剰余を計算するようにしたが、それでもPythonだと時間が足りない。桁があふれた時に、自動的に多倍長整数に拡張する仕様のせいじゃないかと思う。

#include <iostream>
#include <string>

using namespace std;

long long pow( long long a, int b, int c )
{
    long long r = 1;
    for ( int i=0; i<b; i++ )
        r = r * a % c;
    return r;
}

int main()
{
    string bs, ns;
    int c;
    cin >> bs >> ns >> c;

    //  b %= c
    long long b = 0;
    for ( int i=0; i<(int)bs.size(); i++ )
        b = ( b * 10 + bs[i]-'0' ) % c;

    //  n -= 1
    for ( int i=(int)ns.size()-1; ; i-- )
        if ( ns[i] != '0' )
        {
            ns[i] -= 1;
            break;
        }
        else
            ns[i] = '9';

    //  p = (b-1) * b^(n-1) % c
    long long p = 1;
    for ( int i=0; i<(int)ns.size(); i++ )
        p = pow(p,10,c) * pow(b,ns[i]-'0',c) % c;
    p = p * (b+c-1) % c;

    cout << ( p + c - 1 ) % c + 1 << endl;
}