vJudge 273543 – 数论

BASIC KNOWLEDGE

快速幂(mod)

int fp_mod(int a, int n, int m) {
    int ans = 1, temp = a;
    while (n) {
        if (n & 1) {
            ans = ans * temp % m;
        }
        temp = temp * temp % m;
        n >>= 1;
    }
    return ans;
}

乘法取模(mod)

int multi(int a, int b, int m) {
    int ans = 0;
    while (b) {
        if (b & 1) {
            ans = (ans + a) % m;
        }
        a = (a << 1) % m;
        b >>= 1;
    }
    return ans;
}

费马小定理

假如 $a$ 是一个整数， $p$ 是一个质数，那么 $a^{p}-a$ 是 $p$ 的倍数，可以表示为

$a^{p}\equiv a{\pmod {p}}$

如果 $a$ 不是 $p$ 的倍数，这个定理也可以写成

$a^{{p-1}}\equiv 1{\pmod {p}}$

欧拉函数

int phi(int n) {
    int i, res = 1;
    for (i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            res = res * (i - 1);
            n = n / i;
            while (n % i == 0) {
                res = res * i;
                n = n / i;
            }
        }
        if (n == 1) {
            break;
        }
    }
    if (n > 1) {
        res = res * (n - 1);
    }
    return res;
}

欧拉筛法

void gen(int n, vector<int> &primelist, bool check[]) {
    memset(check, 0, sizeof(bool) * n);
    for (int i = 2, u; i < n; i++) {
        if (!check[i]) {
            primelist.push_back(i);
        }
        for (int j = 0; j < primelist.size() && i * primelist[j] < n; j++) {
            u = i * primelist[j];
            check[u] = 1;
            if (i % primelist[j] == 0) {
                break;
            }
        }
    }
}

P1 Sum

费马小定理快速幂取模

PROBLEM

HDU – 4704

ANALYSIS

$n$ 个球放到 $0..n$ 个桶的方案数(mod 1e9+7)。

$\sum_{i=0}^{n-1}\binom{i}{n-1} = 2^{n-1}$

费马小定理降幂。

$a^n \equiv a^{n \mod {p-1}} \pmod p$

证明

$\left\{\begin{matrix} k = \frac{n}{p-1}\\ b = n \mod (p-1) \end{matrix}\right. \Rightarrow n = \frac{k}{p-1}\\$

所以

$a^n \equiv a^{k * (p-1) + b} \pmod p$

即

$a^n \equiv (a^k)^{p-1}*a^b \pmod p$

又

$(a^k)^{p-1} \equiv 1 \pmod p$

所以

$a^n \equiv a^b \pmod p$

得证

SOLUTION

#include <iostream>
#include <cstdio>

using namespace std;

constexpr long long mod = 1e9 + 7;

long long fp_mod(long long a, long long n, long long m) {
    long long ans = 1, temp = a;
    while (n) {
        if (n & 1) {
            ans = ans * temp % m;
        }
        temp = temp * temp % m;
        n >>= 1;
    }
    return ans;
}

int main() {
    for (string s; cin >> s;) {
        long long u = 0, x = 1;
        for (auto it = s.begin(), e = s.end(); it != e; ++it) {
            u *= 10;
            u += *it - '0';
            u %= mod - 1;
        }
        u = (u - 1 + mod - 1) % (mod - 1);
        cout << fp_mod(2, u, mod) << endl;
    }
    return 0;
}

P2 2^x mod n = 1

费马小定理欧拉定理素数筛快速幂取模

PROBLEM

HDU – 1395

ANALYSIS

给出 $n$ ,找出最小的 $x$ 使其满足 $2^{x} \mod n = 1$

假若 $a$ 与 $n$ 互质，那么 $a^{\varphi (n)}-1$ 可被 $n$ n 整除。亦即

$a^{\varphi (n)}\equiv 1{\pmod {n}}$

如果n为质数

其中 $\varphi (n)$ 即为欧拉总计函数。如果 $n$ 为质数，那么 $\varphi (n)=n-1$ ，因此，有高斯的版本：假若 $p$ 为质数， $a$ 与 $p$ 互质（ $a$ 不是 $p$ 的倍数），那么 $a^{p-1}\equiv 1{\pmod {p}}$ 。

这个等式在 $n$ 和 $a$ 互质的时候一定成立

在这个题目中，因为 $a=2$

所以 $n$ 与 $a$ 不互质，除非 $n$ 为偶数，当然 $n=1$ 的时候需要特殊处理下，这些都是小问题，即在 $n$ 为奇数(大于1)的时候一定有解。

暴力的代码太zz了。

如果当 $n$ 为一个非常大的质数，那么暴力就会很慢。因为质数的欧拉函数就是质数-1。

更为高效的方法是： $\varphi(n)$ 进行质因数分解。

然后依次枚举 $\varphi(n)$ 的每一个因子，同时判断这个因子 $x$ 是否满足 $2^{x} \equiv 1 \pmod n$ ，不断更新一个最小值，最后得到答案。

证明：

$a^{x} \equiv 1 \pmod n$ 满足这个方程的最小 $x$ 称为 $a$ 对模 $m$ 的指数。我们记做 $ordm(a)$ ，如果 $ordm(a)==\varphi(n)$ 则我们称 $a$ 为模 $m$ 的原根

有： $a^{x} \equiv 1 \pmod n \Leftrightarrow ordm(a) | X$

根据以上所说： $a^{x} \equiv 1 \pmod n$ 成立，那么 $\varphi(n) \equiv 0 \pmod {ordm(a)}$ 也是成立的

所以 $ordm(a)$ 就是 $\varphi(n)$ 的一个因子

Q.E.D.

SOLUTION

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

int main() {
    int n;
    while (cin >> n) {
        if (n == 1 || n % 2 == 0) {
            printf("2^? mod %d = 1\n", n);
            continue;
        }
        int a = 2, sum = 1;
        while (a != 1) {
            a = (a << 1) % n;
            sum++;
        }
        printf("2^%d mod %d = 1\n", sum, n);
    }
    return 0;
}

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

#define int long long

const int N = 1000000;

int v[N], s[N];
int vcnt, scnt;
int phi[N];
bool check[N];

void gen(int n, int primelist[], bool check[], int phi[]) {
    memset(check, 0, sizeof(bool) * n);
    for (int i = 2, u; i < n; i++) {
        if (!check[i]) {
            primelist[vcnt++] = i;
            phi[i] = i - 1;
        }
        for (int j = 0; j < vcnt && i * primelist[j] < n; j++) {
            u = i * primelist[j];
            check[u] = 1;
            if (i % primelist[j] == 0) {
                phi[u] = phi[i] * primelist[j];
                break;
            } else {
                phi[u] = phi[i] * (primelist[j] - 1);
            }
        }
    }
}

int eular(int n) {
    int i, res = 1;
    for (i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            res = res * (i - 1);
            n = n / i;
            while (n % i == 0) {
                res = res * i;
                n = n / i;
            }
        }
        if (n == 1) {
            break;
        }
    }
    if (n > 1) {
        res = res * (n - 1);
    }
    return res;
}

int fp(int a, int n, int m) {
    int ans = 1, t = a;
    while (n) {
        if (n & 1) {
            ans = ans * t % m;
        }
        t = t * t % m;
        n >>= 1;
    }
    return ans;
}

void exec(int n) {
    if (n < 3 || n % 2 == 0) {
        printf("2^? mod %lld = 1\n", n);
        return;
    }
    int ans, u, f;
    ans = u = f = eular(n);
    int t;
    bool flag = 0;
    do {
        flag = 0;
        scnt = 0;
        f = u;
        for (int i = 0; v[i]*v[i] <= f; i++) {
            while (f % v[i] == 0) {
                s[scnt++] = v[i];
                f /= v[i];
            }
            if (f == 1) {
                break;
            }
        }
        if (f > 1) {
            s[scnt++] = f;
        }
        for (int i = 0; i < scnt; i++) {
            t = s[i];
            if (fp(2, u / t, n) == 1) {
                if (u / t < ans) {
                    ans = u / t;
                }
                flag = 1;
            }
        }
        u = ans;
    } while (flag);
    printf("2^%lld mod %lld = 1\n", ans, n);
}

#undef int
int main() {
#define int long long
    gen(N, v, check, phi);
    for (int i; ~scanf("%lld", &i); exec(i));
    return 0;
}

P3 Dertouzos

费马小定理素数筛

PROBLEM

HDU – 5750

ANALYSIS

找 $x$ 的个数，使得 $d< d*x< n$ 且 $d$ 是 $d*x$ 的最大因子，设 $d$ 的最小素因子为 $m$ ，简单推导知 $x$ 只能取 $[2,\min((n-1)/d, m)]$ 中的素数，而 $\min((n-1)/d$ 至多是 $\sqrt{n}$ 级别，所以只需要预处理出 $5*10^4$ 中所有的素数即可。

可能是我写得不好吧，最后优化了输入输出才过了的。

调了一天bug了，心态有点爆炸，打个微笑脸。

SOLUTION

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

const int N = 60000;
int p[N];
int cnt[N];
bool check[N];
int pcnt;

void gi(int & a) {
    char t = getchar();
    a = 0;
    for (; !isdigit(t); t = getchar());
    for (; isdigit(t); a *= 10, a += t - 48, t = getchar());
}

void gen(int n) {
    memset(check, 0, sizeof(bool) * n);
    pcnt = 0;
    for (int i = 2, u; i < n; i++) {
        cnt[i] = cnt[i - 1];
        if (!check[i]) {
            p[pcnt++] = i;
            cnt[i]++;
        }
        for (int j = 0; j < pcnt && i * p[j] < n; j++) {
            u = i * p[j];
            check[u] = 1;
            if (i % p[j] == 0) {
                break;
            }
        }
    }
}


int exec(int n, int d) {
    if ((n - 1) / 2 < d) {
        return 0;
    }
    int l = 0, r, c, m = d;
    for (int i = 0; i < pcnt && p[i]*p[i] <= d; ++i) {
        if (d % p[i] == 0) {
            m = p[i];
            break;
        }
    }
    m = min((n - 1) / d, m);
    return cnt[m];
}

int main() {
    gen(N);
    int T, a, b;
    cin >> T;
    while (T--) {
        gi(a), gi(b);
        printf("%d\n", exec(a, b));
    }
    return 0;
}

P4 Saving Beans

费马小定理组合数取模卢卡斯定理快速幂

PROBLEM

HDU – 3037

ANALYSIS

将不超过 $m$ 个果子分到 $n$ 个桶中的方案数(mod prime no greater than 1e5)，有序，可空。

可用高中排列组合中隔板法解决。

另设一空桶，问题转化为将 $m+n+1$ 个果子分到 $n+1$ 个桶中，有序，不可空。

易得出 $answer = \binom{n}{n+m}$

问题转化为求 $\binom{n}{n+m} \mod p$

可用卢卡斯定理得出。

卢卡斯定理：

对于非负整数m和n和素数p，同余式:

{\binom {m}{n}}\equiv \prod _{i=0}^{k}{\binom {m_{i}}{n_{i}}}{\pmod {p}},

成立。其中：

m=m_{k}p^{k}+m_{k-1}p^{k-1}+\cdots +m_{1}p+m_{0},

并且

n=n_{k}p^{k}+n_{k-1}p^{k-1}+\cdots +n_{1}p+n_{0}

是m和n的p进制展开。当m < n时，二项式系数 ${\tbinom {m}{n}}=0$ 。

SOLUTION

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include<cstring>

using namespace std;

typedef long long ll;


ll quick_mod(ll a, ll b, ll m) {
    ll ans = 1;
    while (b) {
        if (b & 1) {
            ans = ans * a % m;
        }
        a = a * a % m;
        b >>= 1;
    }
    return ans;
}

ll comp(ll a, ll b, ll m) {
    if (a < b) {
        return 0;
    }
    if (a == b) {
        return 1;
    }
    if (b > a - b) {
        b = a - b;
    }
    ll ans = 1, ca = 1, cb = 1;
    for (int i = 0; i < b; i++) {
        ca = ca * (a - i) % m;
        cb = cb * (b - i) % m;
    }
    ans = ca * quick_mod(cb, m - 2, m) % m;
    return ans;
}

ll lucas(ll a, ll b, ll m) {
    ll ans = 1;
    while (a && b) {
        ans = (ans * comp(a % m, b % m, m)) % m;
        a /= m;
        b /= m;
    }
    return ans;
}

int main() {
    ll t, a, b, m;
    cin >> t;
    while (t--) {
        cin >> a >> b >> m;
        cout << lucas(a + b, b, m) << endl;
    }
    return 0;
}

SUMMARY

emmm

REFERENCE

垃圾CSDN

本作品使用基于以下许可授权：Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.

日	一	二	三	四	五	六
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

BASIC KNOWLEDGE

快速幂(mod)

乘法取模(mod)

费马小定理

欧拉函数

欧拉筛法

P1 Sum

PROBLEM

ANALYSIS

SOLUTION

P2 2^x mod n = 1

PROBLEM

ANALYSIS

SOLUTION

P3 Dertouzos

PROBLEM

ANALYSIS

SOLUTION

P4 Saving Beans

PROBLEM

ANALYSIS

SOLUTION

SUMMARY

REFERENCE

发表回复 取消回复

发表回复取消回复