同余方程(exgcd)

题意

求关于 x 的同余方程 ax = 1(mod b) 的最小正整数解。

思路

ax+by = gcd , x*和y*可以用exgcd()求出

x = x* + k(b/gcd)

y = y* - k(a/gcd)

因为x为最小的正数，所以 x =((x*%b)+b)%b

代码

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
#include<vector>
#include<iostream>
#include<algorithm>
#include <list>
using namespace std;

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

    int d = exgcd(b, a % b, x, y);
    int temp = x;
    x = y;
    y =temp - a / b * x;

    return d;
}

int main()
{
    int a,b,x,y;
    cin>>a>>b;
    exgcd(a,b,x,y);
    cout<<(x%b+b)%b<<endl;
    return 0;
}

总结

x = x* + k(b/gcd)

y = y* - k(a/gcd)

青蛙的约会(exgcd)

思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
a:青蛙a的起点
b:青蛙b的起点
m:青蛙a一次能跳多远
n:青蛙b一次能跳多远
L:一圈的距离
(b-a):a要追b多少米
(m-n):每跳一次，a能追b多少米

x是总共跳了多少次
y是a追b不一定会在一圈内追完，而是追了y圈
          (m - n)*x = b - a + y*L
    (m - n)*x - y*L = b - a
    ———————       —   —————
    已知         已知 已知

扩展欧几里得求的是
    ax+by=d
    a已知，b已知，d是a和b的最大公约数，求x，y
因此把上式的a替换乘(m-n),b替换成L。
式子变成(m-n)*x+(-y)*L=d
如果(b-a)%d不等于0，两只青蛙永远不会碰面
如果(b-a)%d等于零，把(m-n)*x+(-y)*L=d扩大(b-a)/d倍后，x就是结果。

代码

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
32
33
34
35
36
37
#include<vector>
#include<iostream>
#include<algorithm>
#include <list>
using namespace std;
typedef long long LL;

LL exgcd(LL a,LL b,LL &x, LL &y)
{
    if (!b){
        x = 1, y = 0;
        return a;
    }

    LL d = exgcd(b, a % b, x, y);
    LL temp = x;
    x = y;
    y =temp - a / b * x;

    return d;
}

int main()
{
    LL x,y,m,n,l,k,t;
    cin>>x>>y>>m>>n>>l;
    LL gcd = exgcd(n-m,l,k,t);

    if(abs(x-y)%abs(gcd)==0){
        LL bei=(x-y)/gcd;
        l/=abs(gcd);
        printf("%lld\n",(bei*k%l+l)%l);
    }else{
        printf("Impossible\n");
    }
    return 0;
}

总结

gcd可能算出来是负数，记得加abs

最幸运的数字

题意

如果一个数字的每一位都由 8 构成则该数字被称作是幸运数字。

现在给定一个正整数 L，请问至少多少个 8 连在一起组成的正整数（即最小幸运数字）是 L的倍数

思路

求解满足 $L \mid \underbrace{8 \cdots 8}_{x}$ 的最小正整数 $x$
对右边式子进行构造:

于是原问题就变成了求解满足 $9 L I 8 \times\left(10^{x}-1\right)$ 的最小正整数 $x$
由于 8 和 9 互质, 我们设 $d=\operatorname{gcd}(L, 8)$
继续化简 $\frac{9 L}{d} \mathrm{I}\left(10^{x}-1\right)$
这一步不懂得可以看到这来

先不妨令 $A=10^{x}-1$, 则 $9 L \mid 8 A$
又因为 $g c d(8,9)=1$, 所以设 $\operatorname{gcd}(9 L, 8)=\operatorname{gcd}(L, 8)=d$
于是 $\frac{9 L}{d} \mid \frac{8}{d} \cdot A$
又因为 $\operatorname{gcd}\left(\frac{9 L}{d}, \frac{8}{d}\right)=\operatorname{gcd}\left(\frac{L}{d}, \frac{8}{d}\right)=1$
故 $\frac{9 L}{d} \mid A$
令 $C=\frac{9 L}{d}$, 则变成 $C \mid\left(10^{x}-1\right)$
最终变成求解满足 $10^{x} \equiv 1(\bmod C)$ 的最小正整数 $x$
这里的形式有点像欧拉定理: $a^{\varphi(c)} \equiv 1(\bmod c) \quad($ 其中 $\operatorname{gcd}(a, c)=1)$
但是欧拉定理不能保证 $\varphi(n)$ 是满足等式的最小正整数
此处有一个结论: 满足上述式子的最小正整数 $x$ 一定是 $\varphi(c)$ 的约数, 即 $x \mid \varphi(c)$

代码

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <iostream>

using namespace std;

typedef long long LL;

//欧几里得算法
int gcd(LL a, int b) {
    return b ? gcd(b, a % b) : a;
}
//试除法求欧拉函数
LL get_euler(LL c) {
    LL res = c;
    for (int i = 2; i <= c / i; ++ i) {
        if (c % i == 0) {
            int s = 0;
            while (c % i == 0) ++ s, c /= i;
            res = res / i * (i - 1);
        }
    }
    if (c > 1) res = res / c * (c - 1);
    return res;
}
//龟速乘
LL qmul(LL a, LL b, LL c) {
    LL res = 0;
    while (b) {
        if (b & 1) res = (res + a) % c;
        a = (a + a) % c;
        b >>= 1;
    }
    return res;
}
//快速幂
LL qmi(LL a, LL b, LL c) {
    LL res = 1;
    while (b) {
        if (b & 1) res = qmul(res, a, c);
        a = qmul(a, a, c);
        b >>= 1;
    }
    return res;
}
int main() {
    int T = 1;
    LL L;
    while (cin >> L, L) {
        int d = gcd(L, 8);

        LL c = 9 * L / d;

        LL phi = get_euler(c);

        LL res = 1e18;
        if (c % 2 == 0 || c % 5 == 0) res = 0; //判断c和10是否互质(10必须模c余1)
        else {
            for (LL i = 1; i <= phi / i; ++ i) {
                if (phi % i == 0) {
                    if (qmi(10, i, c) == 1) res = min(res, i);
                    if (qmi(10, phi / i, c) == 1) res = min(res, phi / i);
                }
            }
        }
        printf("Case %d: %lld\n", T ++ , res);
    }
    return 0;
}

曹冲养猪(中国剩余定理)

思路

中国剩余定理
设 $x \in Z$, 有

则

代码

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 10;

int n;
int A[N], B[N];

void exgcd(LL a, LL b, LL &x, LL &y)
{
    if (!b) x = 1, y = 0;
    else
    {
        exgcd(b, a % b, y, x);
        y -= a / b * x;
    }
}

int main()
{
    scanf("%d", &n);

    LL M = 1;
    for (int i = 0; i < n; i ++ )
    {
        scanf("%d%d", &A[i], &B[i]);
        M *= A[i];
    }

    LL res = 0;
    for (int i = 0; i < n; i ++ )
    {
        LL Mi = M / A[i];
        LL ti, x;
        exgcd(Mi, A[i], ti, x);
        res += B[i] * Mi * ti;
    }

    cout << (res % M + M) % M << endl;

    return 0;
}