讨论 / C++ TJ
ypfhd 2015-08-07 03:04:52
点我顶贴 收藏 删除
// 10 = 2 * 5

// Lucas + CRT

#include <cstdio>

#include <cstring>

using namespace std;

char s[100005];

int C[10][10], a[100005], N, R5_1, R2_1, R5_2, R2_2;

int Lucas(int m, int n, int p)

{

int Res = 1;

while (m && Res) Res *= C[m % p][n % p] % p, n /= p, m /= p, Res %= p;

return Res;

}

int Pow(int a, int P)

{

int Res = 1;

for (int i = 1; i <= P - 2; i ++) Res *= a, Res %= P;

return Res;

}

int C2[100005], C5[100005];

int main()

{

scanf("%s", s);

N = strlen(s);

for (int i = 0;i < N; i ++) a[i] = s[i] - '0';

C[0][0] = 1;

for (int i = 1; i <= 5; i ++)

{

C[i][0] = 1;

for (int j = 1; j <= i; j ++) C[i][j] = C[i - 1][j] + C[i - 1][j - 1];

}

for (int i = 0; i < N - 1; i ++) C2[i] = Lucas(N - 2, i, 2), C5[i] = Lucas(N - 2, i, 5);

int i5 = Pow(5, 2), i2 = Pow(2, 5);

for (int i = 0; i < N - 1; i ++)

{

R5_1 += a[i] * C5[i], R2_1 += a[i] * C2[i];

R5_2 += a[i + 1] * C5[i], R2_2 += a[i + 1] * C2[i];

R5_1 %= 5, R5_2 %= 5, R2_1 &= 1, R2_2 &= 1;

}

int B1 = R2_1 * 5 * i5 + R5_1 *2 * i2, B2 = R2_2 * 5 * i5 + R5_2 *2 * i2;

B1 %= 10, B2 %= 10;

int Res = B1 * 10 + B2;

if (Res == 0) Res = 100;

printf("%d\n", Res);

return 0;

}

查看更多回复
提交回复