【题解】HackerRank - Number of M-Coprime Arrays

Posted on In Disqus:

题目

https://www.hackerrank.com/challenges/number-of-m-coprime-arrays/problem

题意

求相邻两数互素且数组中每个元素都是 M 的因数的大小为 n 的数组个数。

题解

  • 关键是将 M 分解，每个质因数分开考虑。\((M = \displaystyle \prod_{ i = 1 }^n {p_i}^{ {\alpha}_i})\)
  • 将数组按 \(p_i\) 分解，值不超过 \({\alpha}_i\) 且相邻两数不同时非零。答案即是拆分后每个数组的方案数之积。
  • 求方案数就是线性递推，矩阵快速幂，都是套路。\((a_n = a_{n-1}+ Ca_{n-2}, a_0=1,a_1=C)\)
  • 分解 \(10^{18}\) 的数当然不方便，但是需要的只是指数，所以可以偷懒。（剔除掉所有 \(10^6\) 内的因数后，这个数至多有两个质因数，分类讨论即可。）

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(args...) do { cout << "\033[32;1m" << #args<< " -> "; err(args); } while (0)
#else
#define dbg(...)
#endif
void err() { cout << "\033[39;0m" << endl; }
template<typename T, typename... Args>
void err(T a, Args... args) { cout << a << ' '; err(args...); }
// -----------------------------------------------------------------------------
const LL MOD = 1E9 + 7;

struct Mat {
    static const LL M = 2;
    LL v[M][M];
    Mat() { memset(v, 0, sizeof v); }
    void eye() { FOR (i, 0, M) v[i][i] = 1; }
    LL* operator [] (LL x) { return v[x]; }
    const LL* const operator [] (LL x) const { return v[x]; }
    Mat operator * (const Mat& B) {
        const Mat& A = *this;
        Mat ret;
        FOR (i, 0, M)
            FOR (j, 0, M)
                FOR (k, 0, M)
                    ret[i][j] = (ret[i][j] + A[i][k] * B[k][j]) % MOD;
        return ret;
    }
    Mat pow(LL n) const {
        Mat A = *this, ret; ret.eye();
        for (; n; n >>= 1, A = A * A)
            if (n & 1) ret = ret * A;
        return ret;
    }
    Mat operator + (const Mat& B) {
        const Mat& A = *this;
        Mat ret;
        FOR (i, 0, M)
            FOR (j, 0, M)
                ret[i][j] = (A[i][j] + B[i][j]) % MOD;
        return ret;
    }
    void prt() const {
        FOR (i, 0, M)
            FOR (j, 0, M)
                printf("%lld%c", (*this)[i][j], j == M - 1 ? '\n' : ' ');
    }
};

const LL p_max = 1E6 + 100;
LL prime[p_max], p_sz;
void get_prime() {
    static bool vis[p_max];
    FOR (i, 2, p_max) {
        if (!vis[i]) prime[p_sz++] = i;
        FOR (j, 0, p_sz) {
            if (prime[j] * i >= p_max) break;
            vis[prime[j] * i] = 1;
            if (i % prime[j] == 0) break;
        }
    }
}

LL mul(LL u,LL v, LL p) {
    return (u * v - LL((long double) u * v / p) * p + p) % p;
}

LL pown(LL x, LL n, LL MOD) {
    LL ret = MOD != 1; x %= MOD;
    while (n) {
        if (n & 1) ret = mul(ret, x, MOD);
        x = mul(x, x, MOD);
        n >>= 1;
    }
    return ret;
}

bool checkQ(LL a, LL n) {
    if (n == 2 || a >= n) return 1;
    if (n == 1 || !(n & 1)) return 0;
    LL d = n - 1;
    while (!(d & 1)) d >>= 1;
    LL t = pown(a, d, n);  // 快速乘
    while (d != n - 1 && t != 1 && t != n - 1) {
        t = mul(t, t, n);
        d <<= 1;
    }
    return t == n - 1 || d & 1;
}

bool primeQ(LL n) {
    static vector<LL> t = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};
    if (n <= 1) return false;
    for (LL k: t) if (!checkQ(k, n)) return false;
    return true;
}

LL T, k, n;
int main() {
    LL exp[100], sz;
    get_prime();
    cin >> T;
    while (T--) {
        cin >> k >> n;
        sz = 0;
        FOR (i, 0, p_sz)
            if (n % prime[i] == 0) {
                LL c = 0, p = prime[i];
                while (n % p == 0) {
                    n /= p;
                    ++c;
                }
                exp[sz++] = c;
            }
        if (n > 1) {
            if (primeQ(n)) exp[sz++] = 1;
            else {
                LL t = sqrt(n + 0.5);
                if (t * t == n) exp[sz++] = 2;
                else exp[sz++] = exp[sz++] = 1;
            }
        }
        LL ans = 1;
        FOR (i, 0, sz) {
            Mat x; x[0][0] = x[1][0] = 1; x[0][1] = exp[i];
            x = x.pow(k);
            LL t = x[1][0] * (exp[i] + 1) + x[1][1];
            ans = t % MOD * ans % MOD;
        }
        cout << ans << endl;
    }
}