Pagini recente » Cod sursa (job #48470) | Cod sursa (job #1731657)
#include <bits/stdc++.h>
#define maxN 100002
using namespace std;
int n, m, c, mod, a, b, ans[2][2], mat[2][2];
char s2[maxN], s1[maxN];
vector < int > v;
void mul(int a[2][2], int b[2][2])
{
int i, j, k, res[2][2];
for (i = 0; i < 2; ++ i)
for (j = 0; j < 2; ++ j)
{
res[i][j] = 0;
for (k = 0; k < 2; ++ k)
res[i][j] = (1LL * res[i][j] + 1LL * a[i][k] * b[k][j]) % mod;
}
memcpy(a, res, sizeof(res));
}
void read()
{
freopen("calcul.in", "r", stdin);
fgets(s1, maxN, stdin);
n = strlen(s1) - 1;
fgets(s2, maxN, stdin);
m = strlen(s2) - 1;
scanf("%d", &c);
}
void solve()
{
int i;
mod = 1;
for (i = 1; i <= c; ++ i)
mod *= 10;
for (i = 0; i < n; ++ i)
a = (a * 10 + (s1[i] - '0')) % mod;
for (i = m - 1; i >= 0; -- i)
{
int b, j;
if (s2[i] >= '0' && s2[i] <= '9')
b = s2[i] - '0';
else
b = s2[i] - 'A' + 10;
for (j = 0; j < 4; ++ j)
v.push_back(b & (1 << j));
}
ans[0][1] = ans[1][1] = mat[1][1] = 1;
mat[0][0] = mat[1][0] = a;
for (i = 0; i < v.size(); ++ i)
{
if (v[i])
mul(ans, mat);
mul(mat, mat);
}
}
void write()
{
int i;
freopen("calcul.out", "w", stdout);
printf("%d\n", ans[0][0]);
/*sum = 0;
for (i = 1; i <= b; ++ i)
sum = (1LL * sum + 1LL * lgput(a, i)) % mod;
printf("%d\n", sum);*/
}
int main()
{
read();
solve();
write();
return 0;
}