初等数论

MaxFwl · 2024-07-01 09:08:50 · 算法·理论

数论

P5091 【模板】扩展欧拉定理

模板题。

附代码：

#include <bits/stdc++.h>
#define int long long 
using namespace std;

int a, m, b = 0, phi = 1, flg = 0;
string s;

int Quick_Pow(int a, int b){
    int res = 1;

    while (b){
        if (b & 1)
            res *= a, res %= m;
        a *= a, a %= m;
        b >>= 1;
    }

    return res;
}

signed main(){
    cin >> a >> m;

    int t = m;
    for (int i = 2; i * i <= t; i++){
        if (t % i)  continue;

        phi *= i - 1;
        t /= i;

        while (t % i == 0){
            phi *= i;
            t /= i;
        }
    }

    if (t != 1)
        phi *= t - 1;

    cin >> s;

    for (int i = 0; i < s.length(); i++){
        int u = s[i] - '0';
        b = b * 10 + u;

        if (b >= phi){
            flg = 1;
            b %= phi;
        }
    }

    if (b >= phi){
        flg = 1;
        b %= phi;
    }

    if (flg)
        b += phi;

    cout << Quick_Pow(a, b) << endl;

    return 0;
}

CF510D Fox And Jumping

根据裴蜀定理，只需要选一个最大公因数为 1 的子集即可。

显然可以 01 背包，附代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 310;
int n, l[N], c[N];
map<int, int> mp;

int Gcd(int x, int y){
    if (!y)
        return x;
    return Gcd(y, x % y);
}

signed main(){
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> l[i];
    for (int i = 1; i <= n; i++)
        cin >> c[i];

    for (int i = 1; i <= n; i++){
        map<int, int>::reverse_iterator it;
        for (it = mp.rbegin(); it != mp.rend(); it++){
            int num = (it -> first);
            int val = (it -> second);

            if (!mp.count(Gcd(num, l[i])))
                mp[Gcd(num, l[i])] = val + c[i];
            else    mp[Gcd(num, l[i])] = min(mp[Gcd(num, l[i])], val + c[i]);
        }

        if (!mp.count(l[i]))
            mp[l[i]] = c[i];
        else    mp[l[i]] = min(mp[l[i]], c[i]);
    }

    if (!mp.count(1))
        puts("-1");
    else    cout << mp[1] << endl;

    return 0;
} 

P3807【模板】卢卡斯定理/Lucas 定理

模板题。

附代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e5 + 10;
int T, n, m, p, fac[N<<1];

int Quick_Pow(int x, int y){
    int res = 1;

    while (y){
        if (y & 1)
            res *= x, res %= p;

        x *= x, x %= p;
        y >>= 1;
    }

    return res;
}

int C(int n, int m){
    if (m > n)  
        return 0;

    return fac[n] * Quick_Pow(fac[m], p-2) % p * Quick_Pow(fac[n-m], p-2) % p;
}

int Lucas(int n, int m){
    if (!m)
        return 1;

    return Lucas(n / p, m / p) * C(n % p, m % p) % p;
}

void Solve(){
    cin >> n >> m >> p;
    for (int i = 1; i <= n + m; i++)
        fac[i] = fac[i-1] * i % p;

    cout << Lucas(n + m, n) << endl;
}

signed main(){
    cin >> T;

    fac[0] = 1;
    while (T--)
        Solve();

    return 0;
}

P2480 [SDOI 2010] 古代猪文

模数不是质数，考虑质因数分解，然后使用 CRT 合并。

模数较小的组合数可以用 Lucas 定理处理。

复杂度 O(\sqrt{n} \times \log^2{n})， 附代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int MOD = 999911658;
const int N = 4e4 + 10;
int n, G, r[5], m[5], fac[N], t[10];

void Fac(int mod){
    fac[0] = 1;

    for (int i = 1; i < N; i++)
        fac[i] = fac[i-1] * i % mod;
}

int Quick_Pow(int x, int y, int mod){
    int res = 1;

    while (y){
        if (y & 1)
            res *= x, res %= mod;

        x *= x, x %= mod;
        y >>= 1;
    }

    return res;
}

int C(int n, int m, int mod){
    if (n < m)
        return 0;

    return fac[n] * Quick_Pow(fac[m], mod - 2, mod) % mod * Quick_Pow(fac[n-m], mod - 2, mod) % mod;
}

int Lucas(int n, int m, int mod){
    if (!m)
        return 1;

    return C(n % mod, m % mod, mod) * Lucas(n / mod, m / mod, mod) % mod;
}

int CRT(){
    int res = 0;

    for (int i = 1; i <= 4; i++){
        m[i] = MOD / t[i];
        int y = Quick_Pow(m[i], t[i] - 2, t[i]);

        res += m[i] * y % MOD * r[i] % MOD, res %= MOD;
    }

    return res;
}

signed main(){
    cin >> n >> G;
    if (G == MOD + 1){
        puts("0");
        return 0;
    }

    t[1] = 2;
    t[2] = 3;
    t[3] = 4679;
    t[4] = 35617;

    for (int i = 1; i <= 4; i++){
        Fac(t[i]);

        for (int d = 1; d * d <= n; d++){
            if (n % d)
                continue;

            r[i] += Lucas(n, d, t[i]), r[i] %= t[i];

            if (d * d == n)
                break;

            r[i] += Lucas(n, n / d, t[i]), r[i] %= t[i];
        }
    }

    int mi = CRT();
    cout << Quick_Pow(G, mi, MOD + 1) << endl;

    return 0;
}

P3868 [TJOI 2009] 猜数字

基本就是裸的 CRT。

附代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 15;
int n, a[N], m[N], b[N];

int Quick_Mul(int x, int y, int mod){
    int res = 0;

    while (y){
        if (y & 1)
            res += x, res %= mod;

        x += x, x %= mod;
        y >>= 1;
    }

    return res;
}

void Ex_Gcd(int a, int b, int& x, int& y){
    if (b == 0){
        x = 1;
        y = 0;
        return;
    }

    Ex_Gcd(b, a % b, x, y);

    int t = x;
    x = y;
    y = t - a / b * y;
}

int CRT(){
    int res = 0;
    int mul = 1;

    for (int i = 1; i <= n; i++)
        mul *= b[i];

    for (int i = 1; i <= n; i++){
        m[i] = mul / b[i];

        int x, y;
        Ex_Gcd(m[i], b[i], x, y);

        x = (x % b[i] + b[i]) % b[i];

        res += Quick_Mul(Quick_Mul(m[i], x, mul), a[i], mul), res %= mul;
    }

    return res;
}

signed main(){
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
        cin >> b[i];

    for (int i = 1; i <= n; i++){
        a[i] = (a[i] % b[i] + b[i]) % b[i];
        //cout << a[i] << endl;
    }

    cout << CRT() << endl;

    return 0;
}

UVA11526 H(n)

数论分块模板。

附代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;

int T, n;

int H(int x){
    int res = 0;

    int l = 1, r;
    while (l <= n){
        r = n / (n / l);

        res += (r - l + 1) * (n / l);

        l = r + 1;
    }

    return res;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> T;

    while (T--){
        cin >> n;

        cout << H(n) << endl;
    }

    return 0;
}

CF1954E Chain Reaction

二维数论分块模板。

附代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int n, mx = 0, a[N];
long long ans[N];

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> a[i];
        mx = max(mx, a[i]);
    }

    for (int i = 0; i < n; i++)
        for (int l = 1, r; ; l = r + 1){
            int r1 = (l < a[i] ? (a[i]-1) / ((a[i]-1) / l) : N);
            int r2 = (l < a[i+1] ? (a[i+1]-1) / ((a[i+1]-1) / l) : N);

            r = min(r1, r2);

            if (r == N)
                break;

            int x = (a[i+1] - 1) / l - max(a[i] - 1, 0) / l;

            if (x > 0){
                ans[l] += x;
                ans[r+1] -= x;
            }
        }

    ++ans[0];

    for (int i = 1; i <= mx; i++){
        ans[i] += ans[i-1];
        cout << ans[i] << " " ;
    }

    return 0;
}

P2261 [CQOI2007] 余数求和

数论分块然后特判即可。

附代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;

int n, k, ans = 0;

signed main(){
    cin >> n >> k;
    ans += k * n;

    for (int l = 1, r; l <= n; l = r + 1){
        if (k / l != 0)
            r = min(n, k / (k / l));
        else    break;

        int x = k / l;
        int num = (l + r) * (r - l + 1) / 2;

        ans -= x * num;
    }

    cout << ans << endl;

    return 0;
}

P4139 上帝与集合的正确用法

根据扩展欧拉定理，可以转化为递归问题。

需要线性筛预处理欧拉函数。

附代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e7 + 10;
const int M = 1e6 + 10;
int T, p, tot = 0, phi[N], prime[M];
bool flg[N];

int Quick_Pow(int x, int y, int mod){
    int res = 1;

    while (y){
        if (y & 1)
            res *= x, res %= mod;

        x *= x, x %= mod;

        y >>= 1;
    }

    return res;
}

int Work(int p){
    if (p == 1)
        return 0;

    return Quick_Pow(2, Work(phi[p]) + phi[p], p);
}

void Solve(){
    cin >> p;

    cout << Work(p) << endl;
}

signed main(){
    phi[1] = 1;
    for (int i = 2; i < N; i++){
        if (!flg[i]){
            prime[++tot] = i;
            phi[i] = i - 1;
        }

        for (int j = 1; j <= tot && i * prime[j] < N; j++){
            flg[i * prime[j]] = 1;

            if (i % prime[j] == 0){
                phi[i*prime[j]] = phi[i] * prime[j];
                break;
            }else   phi[i*prime[j]] = phi[i] * (prime[j] - 1);
        }
    }

    cin >> T;

    while (T--)
        Solve();

    return 0;
}