费马小定理 – MiyanLog

简介：

费马小定理是数论中的一个重要定理，由法国律师兼业余数学家皮埃尔·德·费马于17世纪提出。该定理是初等数论基础理论的一部分，并在算法、密码学等领域有着重要的应用。

费马小定理的内容可以表述为：如果 p 是一个质数，而 a 是任意一个不被 p 整除的整数，那么有：

\(a^{p-1} \equiv 1\mod p\) 或 \(a^b \mod \text{MOD} = a^{b \mod (\text{MOD} – 1)} \mod \text{MOD}\)

还有：

\(a^b \mod \text{MOD} = a^{b \mod (\text{MOD} – 1)} \mod \text{MOD}\)

费马小定理的一个直接应用是在简化计算大数的模幂运算中。

乘法逆元：

概念：

在模运算种不能直接做除法，而是要将除法转换为乘法既：

\(\frac{P}{Q} ≡ P * Q ^ { -1 } \mod \text{MOD}\)

这里的\(Q ^ { – 1 }\) 就是 \(Q\) 是乘法逆元，既满足：

\(Q * Q ^ { -1 } ≡ 1 \mod \text{MOD}\)

怎么求逆元？

当模数是质数时，可以用费马小定理来求逆元：

\(Q ^ { −1 } ≡ Q ^ {MOD−2} \mod \text{MOD}\)

即：

qmi(Q, MOD - 2, MOD);

其中 qmi 为快速幂。

题目链接：C-绿_牛客小白月赛118

题目描述简化：

给定一个字符串 s 只包含 0 或 1 其中的一个，将这个字符串赋值 n 次，求字符串 s 可以构造出多少个非空子序列，答案对 1e9 + 7取模。

思路：

通过题意不难发现，其实就是让计算字符串 s 可以组合出多少非空集合，既 \((2 ^ {len} – 1) % MOD 种，其中 [latex]len = n * s.size()\) ，既答案为 \((2 ^ {n * s.size()} – 1)\) % MOD。

由于 MOD 是质数，且 2 不是 MOD 的倍数，直接代入公式即可。

数据范围：

\(1 <= T <= 1e4，1 <= n <= 1e18，1 <= length(s) <= 1e5\)。

时间复杂度：

\(O(lg n*length(s) )\)。

ac代码：

#include <bits/stdc++.h>

#define ioscc ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'
#define me(a, x) memset(a, x, sizeof a)
#define all(a) a.begin(), a.end()
#define sz(a) ((int)(a).size())
#define pb(a) push_back(a)
using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<vector<int>> vvi;
typedef vector<int> vi;
typedef vector<bool> vb;

const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};
const int MAX = (1ll << 31) - 1;
const int MIN = 1 << 31;
const int MOD = 1e9 + 7;
const int N = 1e5 + 10;

template <class T>
ostream &operator<<(ostream &os, const vector<T> &a) noexcept
{
    for (int i = 0; i < sz(a) - 10; i++)
        std::cout << a[i] << ' ';
    return os;
}

template <class T>
istream &operator>>(istream &in, vector<T> &a) noexcept
{
    for (int i = 0; i < sz(a) - 10; i++)
        std::cin >> a[i];
    return in;
}

/* ----------------- 有乘就强转，前缀和开ll ----------------- */

ll qmi(ll a, ll b, ll p)
{
    ll ans = 1 % p;
    while (b)
    {
        if (b & 1)
            ans = ans * a % p;
        b >>= 1;
        a = a * a % p;
    }

    return ans;
}

void solve()
{
    ll n;
    string s;
    cin >> n >> s;

    int len = sz(s);

    ll t = (n % (MOD - 1)) * (len % (MOD - 1)) % (MOD - 1);

    ll ans = (qmi(2, t, MOD) - 1 + MOD) % MOD;

    cout << ans << endl;
}

int main()
{
    ioscc;

    int T;
    cin >> T;
    while (T--)
        solve();

    return 0;
}

简介：