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}-ap的倍数,可以表示为

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

 

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

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

 

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

这个等式在na互质的时候一定成立

在这个题目中,因为a=2

所以na不互质,除非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< ndd*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} \]

mnp进制展开。当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

  1. https://blog.csdn.net/a27038/article/details/77129556
  2. https://blog.csdn.net/xieshimao/article/details/6688618
  3. https://blog.csdn.net/xh_reventon/article/details/8690691
  4. https://blog.csdn.net/V5ZSQ/article/details/52021261

CC BY-NC-SA 4.0 本作品使用基于以下许可授权:Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.

发表评论

您的电子邮箱地址不会被公开。