Kalorona

P3846:「TJOI2007」可爱的质数题解

BSGS 算法模板题

有\(a^{x} \equiv b (mod \; p)\)，求\(x\)的值。我们可以来推下这个式子，首先，这个\(x \in [0, p]\)，我们可以设\(x=im-j\)，其中\(m=\lceil \sqrt{p} \rceil\)。显然，\(j \in [0, m], i \in [1, m]\)。式子变成这个样子：

\[a^{im}\equiv a^j b (mod \; p)\]

然后我们只需要求出后半部分，压入 map 中，再枚举前半部分即可求出。

代码

// P3846.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll p, a, b;
ll quick_power(ll base, ll tim)
{
    ll tmp = 1;
    while (tim)
    {
        if (tim & 1)
            tmp = tmp * base % p;
        base = base * base % p;
        tim >>= 1;
    }
    return tmp;
}
map<ll, ll> hashTable;
int main()
{
    scanf("%lld%lld%lld", &p, &a, &b);
    a %= p;
    if (a == 0)
    {
        if (b == 0)
            printf("0");
        else
            printf("no solution");
        return 0;
    }
    hashTable.clear();
    ll m = ceil(sqrt(p));
    for (int j = 0, x = 1; j <= m; j++, x = x * a % p)
        hashTable[x * b % p] = j;
    ll unit = quick_power(a, m);
    for (int i = 1, x = unit; i <= m; i++, x = x * unit % p)
        if (hashTable.count(x))
        {
            printf("%lld", i * m - hashTable[x]);
            return 0;
        }
    printf("no solution");
    return 0;
}

CH3101:阶乘分解题解

数学思路

最近要开始学一些数学方面的东西了，这题作为基础题再好不过了。首先，这道题问的就是在阶乘\(N!=1*2*3*\dots *N\)中分解质因数。我们可以先求出\([1,N]\)范围内的质数，然后再来求出这个式子中质因数的次数。

memset(isPrime, true, sizeof(isPrime));
isPrime[1] = false;
for (int i = 2; i <= n; i++)
    if (isPrime[i])
    {
        primes.push_back(i);
        for (int factor = 2; factor * i <= n; factor++)
            isPrime[i * factor] = false;
    }

接下来，我们可以说明，在阶乘式中，对于一个素数\(p\)，它的一次项出现次数为\( \lfloor \frac {N} {p} \rfloor \)，则二次项出现的次数为\(\lfloor \frac {N} {p^2} \rfloor\)，归纳起来，可以得到：

\[ \lfloor \frac {N} {p} \rfloor + \lfloor \frac {N} {p^2} \rfloor + \lfloor \frac {N} {p^3} \rfloor + \dots + + \lfloor \frac {N} {p^{log_{p} N}} \rfloor\]

化为循环式，得到：

\[ \sum_{p^i \leq N}^{i = 1} \; \lfloor \frac {N} {p^i} \rfloor\]

详细看代码吧：

// CH3101.cpp
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <vector>
#define uint unsigned int
using namespace std;
const int MX_N = 5e6 + 100;
bool isPrime[MX_N];
uint n, cs[MX_N];
vector<uint> primes;
int main()
{
    scanf("%u", &n);
    memset(isPrime, true, sizeof(isPrime));
    isPrime[1] = false;
    for (int i = 2; i <= n; i++)
        if (isPrime[i])
        {
            primes.push_back(i);
            for (int factor = 2; factor * i <= n; factor++)
                isPrime[i * factor] = false;
        }
    int siz = primes.size();
    for (int i = 0; i < siz; i++)
    {
        uint c = 0;
        for (int num = n; num; num /= primes[i])
            c += num / primes[i];
        printf("%u %u\n", primes[i], c);
    }
    return 0;
}