题目
Luogu
LOJ
思路
代码
#include <iostream>
#include <cstring>
using namespace std;
const int N = 110, M = 2e7 + 10, mod = 20170408;
int n, m, p, P[M], V[M], idx, cnt[N];
struct MATRIX { int a[N][N]; };
MATRIX operator*(MATRIX A, MATRIX B) {
static MATRIX C;
memset(C.a, 0, sizeof C.a);
for (int i = 0; i < p; i++)
for (int j = 0; j < p; j++)
for (int k = 0; k < p; k++)
C.a[i][j] = (C.a[i][j] + 1ll * A.a[i][k] * B.a[k][j]) % mod;
return C;
}
void init(int n) {
V[1] = true;
for (int i = 2; i <= n; i++) {
if (!V[i]) P[++idx] = i;
for (int j = 1; P[j] <= n / i; j++) {
V[P[j] * i] = true;
if (i % P[j] == 0) break;
}
}
}
MATRIX qmi(MATRIX A, int b) {
static MATRIX C;
memset(C.a, 0, sizeof C.a);
for (int i = 0; i < p; i++) C.a[i][i] = 1;
for (; b; b >>= 1, A = A * A)
if (b & 1) C = C * A;
return C;
}
MATRIX work(int inv) {
static MATRIX A, F;
memset(cnt, 0, sizeof cnt);
memset(F.a, 0, sizeof F.a);
for (int i = 1; i <= m; i++)
if (inv == 1) cnt[i % p]++;
else if (inv == 2 && V[i]) cnt[i % p]++;
for (int i = 0; i < p; i++)
for (int j = 0; j < p; j++)
A.a[i][j] = cnt[(j - i + p) % p];
F.a[0][0] = 1;
return F * qmi(A, n);
}
int main() {
init(M - 10);
cin >> n >> m >> p;
cout << ((work(1).a[0][0] - work(2).a[0][0]) % mod + mod) % mod << endl;
return 0;
}