习题

洛谷P2388CF27E洛谷P5493洛谷P7325

求 \(\prod {n!}\) 中因子 \(k\) 的个数 \(O(n\cdot\log{n})\)

代码

C++
i64 get(i64 n, i64 k) {
    i64 ans = 0;
    i64 num = k;
    while (num <= n) {
        i64 z = n / num;
        ans += num * z * (z - 1) / 2;
        ans += z * (1 + n % num);
        num *= k;
    }
    return ans;
}

Problem - E - Codeforces

求约数个数为 \(k\) 的最小数 \(k\leq1000\)

代码

C++
using i64 = long long;
using u64 = unsigned long long;
vector<int> prime{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
const int N = prime.size();
const i64 INF = 0x7fffffffffffffff;
int k;
i64 dfs(int idx, u64 sum, int num) {
    if (num > k || idx == N) {
        return INF;
    }
    if (num == k) {
        return sum;
    }
    i64 res = INF;
    for (int i = 1 ; i < 64 ; i++) {
        if (sum * prime[idx] > res) break;
        sum *= prime[idx];
        res = min(res, dfs(idx + 1, sum, num * (i + 1)));
    }
    return res;
}
int main() {
    cin >> k;
    cout << dfs(0, 1, 1);
    return 0;
}

P5493 质数前缀统计 - 洛谷

\(\sum_{i=1}^{\lfloor\sqrt{N}\rfloor}i^2\cdot{S(\lfloor\frac{N}{i}\rfloor)}\)

\(S(n)\) 为 \(n\) 以内质数的 \(C\) 次方和

代码

C++
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
i64 P, mod;
i64 qpow(i64 a, i64 b) {
    long long res = 1;
    while (b) {
        if (b & 1) res = res * a % P;
        a = a * a % P;
        b >>= 1;
    }
    return res;
}
namespace Larange {
    const int N = 13;
    i64 fact[N], invf[N], pre[N], suf[N], f[N];
    int m;
    void init(int C) {
        m = C + 2;
        fact[0] = 1;
        for (int i = 1 ; i <= m ; i++) {
            fact[i] = fact[i - 1] * i % P;
            f[i] = (f[i - 1] + qpow(i, C)) % P;
        }
        invf[m] = qpow(fact[m], P - 2);
        for (int i = m - 1 ; i >= 0 ; i--) {
            invf[i] = invf[i + 1] * (i + 1) % P;
        }
    }
    i64 get(i64 v) {
        if (v <= m) return f[v];
        v %= P;
        pre[0] = 1;
        for (int i = 1 ; i <= m ; i++) {
            pre[i] = pre[i - 1] * (v - i) % P;
        }
        suf[m + 1] = 1;
        for (int i = m ; i >= 1 ; i--) {
            suf[i] = suf[i + 1] * (v - i) % P;
        }
        i64 res = 0;
        for (int i = 1 ; i <= m ; i++) {
            i64 s1 = pre[i - 1] * suf[i + 1] % P;
            i64 s2 = invf[i - 1] * invf[m - i] % P;
            if ((m - i) & 1) {
                s2 = P - s2;
            }
            res = (res + s1 * s2 % P * f[i] % P + P) % P;
        }
        return res;
    }
} // Larange
i64 g0[200005], g1[200005];
i64 add(i64 x, i64 y) {
    return x + y >= P ? x + y - P : x + y;
}
i64 sub(i64 x, i64 y) {
    return x - y < 0 ? x - y + P : x - y;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    i64 n;
    int C;
    cin >> n >> C >> P;
    i64 sqr = sqrtl(n);
    Larange::init(C);
    for (int i = 1 ; i <= sqr ; i++) {
        g0[i] = sub(Larange::get(i), 1);
        g1[i] = sub(Larange::get(n / i), 1);
    }
    for (int i = 2 ; i <= sqr ; i++) {
        if (g0[i] == g0[i - 1]) continue;
        i64 pc = qpow(i, C), pg = g0[i - 1];
        i64 L1 = sqr / i, L2 = min(n / i / i, sqr);
        L1 = min(L1, L2);
        for (int j = 1 ; j <= L1 ; j++) {
            g1[j] = sub(g1[j], pc * sub(g1[j * i], pg) % P);
        }
        i64 temp = n / i;
        for (int j = L1 + 1 ; j <= L2 ; j++) {
            g1[j] = sub(g1[j], pc * sub(g0[temp / j], pg) % P);
        }
        i64 st = 1LL * i * i;
        for (int j = sqr ; j >= st ; j--) {
            g0[j] = sub(g0[j], pc * sub(g0[j / i], pg) % P);
        }
    }
    i64 ans = 0;
    for (int i = 1 ; i <= sqr ; i++) {
        ans = add(ans, g1[i] * i % P * i % P);
    }
    cout << ans << "\n";
    return 0;
}

P7325 [WC2021] 斐波那契 - 洛谷

定义 \(F_0=a,F_1=b,F_i=(F_{i-1}+F_{i-2})\mod m\)

给定 \(a\) 和 \(b\) 和 \(m\), 问 \(F_p\mod m = 0\) 的最小的整数 \(p\)

代码

C++
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
void Exgcd(i64 a, i64 b, i64 &x, i64 &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return;
    }
    Exgcd(b, a % b, y, x);
    y -= a / b * x;
}
int inv(int a, int P) {
    i64 x, y;
    Exgcd(a, P, x, y);
    return (x % P + P) % P;
}
struct Node {
    int x, y, z;
    bool operator<(const Node &node) const {
        if (x == node.x) {
            if (y == node.y) {
                return z < node.z;
            }
            return y < node.y;
        }
        return x < node.x;
    }
};
map<Node, int> ans[100005];
int n, m;
int solve(int a, int b) {
    if (a == 0) return 0;
    if (b == 0) return 1;
    int d = __gcd(__gcd(a, b), m);
    int m1 = m / d;
    a /= d;
    b /= d;
    int p = __gcd(a, m1), q = __gcd(b, m1), m2 = m1 / p / q;
    a /= p;
    b /= q;
    int k = 1LL * a * inv(b, m2) % m2;
    if (ans[m1].count({k, q, p})) return ans[m1][{k, q, p}];
    return -1;
}
int main() {
    cin >> n >> m;
    for (int m1 = 2 ; m1 <= m ; m1++) {
        if (m % m1 == 0) {
            int a = 0, b = 1;
            for (int j = 0 ; ; j++) {
                if (a && b) {
                    int p = __gcd(a, m1), q = __gcd(b, m1), m2 = m1 / p / q;
                    int ta = a / p, tb = b / q;
                    int k = 1LL * ta * inv(tb, m2) % m2;
                    if (!ans[m1].count({k, q, p})) {
                        ans[m1][{k, q, p}] = j;
                    }
                }
                int x1 = b;
                b = a;
                a = (x1 + a) % m1;
                if (b == 1 && a == 0) {
                    break;
                }
            }
        }
    }
    for (int i = 0 ; i < n ; i++) {
        int a, b;
        cin >> a >> b;
        a %= m;
        b = (m - b % m) % m;
        cout << solve(a, b) << "\n";
    }
    return 0;
}