数论基础练习题解

Hello_World

exgcd

扩展欧几里得要解决的就是求解 $ax+by=c$ 整数解的问题。
首先证明：若方程有整数解，则 $c$ 必然为 $\gcd(a,b)$ 的整数倍。

设 $a=p_a\times\gcd(a,b),b=p_b\times\gcd(a,b)$，则 $ax+by=\gcd(a,b)\times(p_ax+p_by)=c$，又因为 $p_a,p_b,x,y$ 都是整数，所以 $c$ 必然是 $\gcd(a,b)$ 的整数倍。

进而求解：方程 $ax+by=\gcd(a,b)$ 的整数解。

$$\begin{array}\\ ax+by&=&\gcd(a,b)\\ &=&\gcd(b,a\%b)\\ &=&bx'+a\%b\times y'\\ &=&bx'+(a-\lfloor\frac{a}{b}\rfloor\times b)\times y'\\ &=&ay'+b\times(x'-\lfloor\frac{a}{b}\rfloor\times y') \end{array}$$
比较系数可得：$x=y',y=x'-\lfloor\frac{a}{b}\rfloor\times y'$，当 $b=0$ 时，$\gcd(a,b)=a$，此时 $x=1,y=0$ 即为方程 $ax+by=\gcd(a,b)(b=0)$ 的解。

所以可以得出 $exgcd$ 代码如下：

#define LL long long
LL exgcd(LL a, LL b, LL &x, LL &y) {
    if(b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    LL gcd = exgcd(a, b, x, y);
    LL tmp = x;
    x = y;
    y = tmp - a / b * y;
    return gcd;
}

还可以通过判断 $c$ 是否是返回值 $\gcd(a,b)$ 的倍数，来计算 $ax+by=c$ 的解：

LL cal(LL a, LL b, LL c) {
    LL x, y;
    LL gcd = exgcd(a, b, x, y);
    if(c % gcd != 0) {
        return -1;
    }
    LL MOD = abs(b / gcd);
    return (x % MOD + MOD) % MOD;
}

该函数的功能是计算方程 $ax+by=c$ 的 $x$ 的最小非负整数解，若无解，则返回 $-1$。注意这里 $x$ 的下一个整数解为 $x\pm\frac{b}{\gcd(a,b)}$，而不是 $x\pm b$，读者请自行证明。
要得到 $x,y$ 的解，且 $x$ 为最小非负整数解，则 $cal$ 函数也可以写为：

bool cal(LL a, LL b, LL c, LL &x, LL &y) {
    LL gcd = exgcd(a, b, x, y);
    if(c % gcd != 0) {
        return false;
    }
    LL MOD = abs(b / gcd);
    x = (x % MOD + MOD) % MOD;
    y = (c - a * x) / b;
    return true;
}

2 月 26 日 数论基础练习

A. Sum of Consecutive Prime Numbers

题意

一个数字 $n$ 可能可以由几个连续的素数相加得到，给定 $n$，求有几种连续的素数和为 $n$。

数据范围

$2\leq n\leq10000$

题解

素数打表，然后对素数做前缀和，$O(n)$ 枚举起点，对于每个起点二分查找终点。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 10000 + 100;
int n;
bool vis[maxn];
int prime[maxn];
int sum[maxn];
int *it;
void Prime(int n) {
    for(LL i = 2; i < n; ++i) {
        if(!vis[i]) {
            prime[++prime[0]] = i;
        }
        for(int j = 1; j <= prime[0] && i * prime[j] < n; ++j) {
            int k = i * prime[j];
            vis[k] = true;
            if(i % prime[j] == 0) {
                break;
            }
        }
    }
    for(int i = 1; i <= prime[0]; ++i) {
        sum[i] = sum[i - 1] + prime[i];
    }
}
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    Prime(maxn);
    while(scanf("%d", &n), n != 0) {
        int ans = 0;
        for(int i = 0; i == 0 || prime[i] < n; ++i) {
            it = lower_bound(sum, sum + prime[0] + 1, sum[i] + n);
            if(*it == sum[i] + n) {
                ++ans;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

B. Romantic

题意

给定 $a,b$，计算 $ax+by=1$ 的最小非负整数解，若无解则输出“$sorry$”。

数据范围

$0<a,b\leq2^{31}$

题解

$exgcd$ 裸题。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
LL a, b;
LL exgcd(LL a, LL b, LL &x, LL &y) {
    if(b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    LL d = exgcd(b, a % b, x, y);
    LL tmp = x;
    x = y;
    y = tmp - a / b * y;
    return d;
}
LL cal(LL a, LL b, LL c) {
    LL x, y;
    LL gcd = exgcd(a, b, x, y);
    if(gcd != 1) {
        return INT_MIN;
    }
    b = abs(b);
    return (x % b + b) % b;
}
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    while(scanf("%lld%lld", &a, &b) != EOF) {
        LL ans = cal(a, b, 1);
        if(ans == INT_MIN) {
            printf("sorry\n");
        } else {
            printf("%lld %lld\n", ans, (1 - a * ans) / b);
        }
    }
    return 0;
}

C. Raising Modulo Numbers

题意

有 $Z$ 组数据，每组数据有 $H$ 组 $A,B$ 值，计算 $\sum_{i=1}^H(A_i^{B_i})\mod M$ 的值。

数据范围

$1\leq M\leq45000,1\leq H\leq45000$

题解

快速幂裸题。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
int T, n;
LL MOD, a, b, ans;
LL fast_pow(LL res, LL n) {
    LL ans;
    for(ans = 1; n != 0; n >>= 1) {
        if((n & 1) == 1) {
            ans = (ans * res) % MOD;
        }
        res = (res * res) % MOD;
    }
    return ans;
}
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    scanf("%d", &T);
    while(T--) {
        ans = 0;
        scanf("%lld%d", &MOD, &n);
        for(int i = 0; i < n; ++i) {
            scanf("%lld%lld", &a, &b);
            ans += fast_pow(a, b);
            ans %= MOD;
        }
        printf("%lld\n", ans);
    }
    return 0;
}