You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
54 lines
1.3 KiB
C++
54 lines
1.3 KiB
C++
#include <cstdio>
|
|
#include <cstring>
|
|
using namespace std;
|
|
struct mat
|
|
{
|
|
int d[2][2];
|
|
const mat &operator=(const mat &rhs)
|
|
{
|
|
memcpy(this, &rhs, sizeof(rhs));
|
|
return *this;
|
|
}
|
|
const mat &operator*=(const mat &rhs)
|
|
{
|
|
mat ret;
|
|
memset(&ret, 0, sizeof(ret));
|
|
for (int i = 0; i < 2; i++)
|
|
for (int j = 0; j < 2; j++)
|
|
for (int k = 0; k < 2; k++)
|
|
ret.d[i][j] += d[i][k] * rhs.d[k][j], ret.d[i][j] %= 7;
|
|
memcpy(this, &ret, sizeof(ret));
|
|
return *this;
|
|
}
|
|
};
|
|
template <typename T>
|
|
void fpow(T &ans, const T &a, int b)
|
|
{
|
|
for (T x = a; b; b >>= 1)
|
|
{
|
|
if (b & 1)
|
|
ans *= x;
|
|
x *= x;
|
|
}
|
|
}
|
|
int main()
|
|
{
|
|
int a, b, n;
|
|
while (scanf("%d%d%d", &a, &b, &n), a | b | n)
|
|
if (n <= 2)
|
|
puts("1");
|
|
else
|
|
{
|
|
mat ans, mul;
|
|
ans.d[0][0] = ans.d[1][1] = 1;
|
|
ans.d[0][1] = ans.d[1][0] = 0;
|
|
mul.d[0][0] = a;
|
|
mul.d[0][1] = b;
|
|
mul.d[1][0] = 1;
|
|
mul.d[1][1] = 0;
|
|
fpow(ans, mul, n - 2);
|
|
printf("%d\n", (ans.d[0][0] + ans.d[0][1]) % 7);
|
|
}
|
|
return 0;
|
|
}
|