x와 y의 최대공약수가 d일 때 (x,y)=d 방정식으로 변환하면 ax+by=d 매개변수 x와 y에 대한 표현식 x y의 부호는 상관없음 x=x0+kb/d (반대쪽을 더함) y=y0-ka/d

//확장 유클리드 알고리즘
int extended_gcd(int a, int b, int &x, int &y)//ax=d%(mod b) x와 y는 ax+by=d 방정식의 한 해  반환값은 최대공약수(마지막 레이어의 a)
{
    if (!b)
    {
        x = 1, y = 0;
        return a;
    }

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

    return d;
}

동일 방정식 ax=1(mod d)의 x 정수해 구하기 여기서 최대공약수는 1 ax+yd=1

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

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

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

    return d;
}

int main()
{
    int a, b;
    cin >> a >> b;

    int x, y;
    extended_gcd(a, b, x, y);

    cout << (x % b + b) % b << endl;

    return 0;
}

개구리 만남 문제 원형으로 a는 a점에서 한번에 m미터, b는 b점에서 한번에 n미터 이동 L이 원의 둘레 x초 후 b를 따라잡는 경우

https://www.acwing.com/activity/content/problem/content/1753/ 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 + yL (m - n)x - yL = b - a ——————— — ————— 값 알려짐 값 알려짐 값 알려짐

확장 유클리드는 ax+by=d의 해를 구함 a, b, d가 a와 b의 최대공약수일 때 x, y를 구함 따라서 위 식에서 a를(m-n), b를 L로 대체 식은 (m-n)*x+(-y)*L=d가 됨 LL d = extended_gcd(m - n, L, x, y); (b-a)%d가 0이 아니면 두 개구리는 만날 수 없음 (최대공약수가 아님) (b-a)%d가 0이면 (m-n)x+(-y)L=d를 (b-a)/d배 확장하면 x가 해가 됨 //x0가 확장되는 이유는 x0가 (m-n)x-yl=gcd(m-n,l) 방정식의 해이고 //답은 (m-n)x-yl=b-a를 만족하는 x0이기 때문에 다른 x0이므로 확장이 필요

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

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

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

    return d;
}

int main()
{
    LL a, b, m, n, L;
    cin >> a >> b >> m >> n >> L;

    LL x, y;
    LL d = extended_gcd(m - n, L, x, y);
    if ((b - a) % d) puts("Impossible");
    else
    {
        x *= (b - a) / d;
        LL t = abs(L / d);
        cout << (x % t + t) % t << endl;
    }

    return 0;
}

가장 행운의 수 몇 개의 8이 연결되어 c의 배수가 되는지 https://www.acwing.com/problem/content/204/

9L |8×(10^x−1）를 만족하는 최소 정수 x 찾기 최종적으로 10^x≡1(modC)를 만족하는 최소 정수 x를 구하는 문제로 변환

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

using namespace std;

typedef long long LL;

LL fast_multiply(LL a, LL k, LL p) {
    LL res = 0;
    while (k) {
        if (k & 1) res = (res + a) % p;
        k >>= 1;    
        a = (a + a) % p;
    }
    return res;
}

LL euler_phi(LL C) {
    LL res = C;
    for (LL i = 2; i <= C / i; i ++ ) 
        if (C % i == 0) {
            while (C % i == 0) C /= i;
            res = res / i * (i - 1);
        }
    if (C > 1) res = res / C * (C - 1);
    return res;
}

LL fast_pow(LL a, LL k, LL p) {
    LL res = 1;
    while (k) {
        if (k & 1) res = fast_multiply(res, a, p);
        k >>= 1;
        a = fast_multiply(a, a, p);
    }
    return res;
}

LL gcd(LL a, LL b) {
    return b ? gcd(b, a % b) : a;
}

int main() {
    int T = 1;
    LL L;
    while (cin >> L, L) {
        int d = 1;
        while (L % (d * 2) == 0 && d * 2 <= 8) d *= 2;
        // C와 phi(C) 계산
        LL C = 9 * L / d;
        LL phi = euler_phi(C);

        LL res = 1e18;

        // gcd는 일정한 상수를 가짐, C가 큼 
        // if (gcd(10, C) != 1) res = 0;
        // 10과 C가 서로소인지 판단, 아니면 0 출력
        if (C % 2 == 0 || C % 5 == 0) res = 0;

        // phi(C)의 모든 약수 열거
        for (LL d = 1; d * d <= phi; d ++ ) // 약수 d는 int 범위를 넘을 수 있음 제곱근으로 열거
            if (phi % d == 0) {//약수이면
                if (fast_pow(10, d, C) == 1) res = min(res, d);//나머지가 1이면
                if (fast_pow(10, phi / d, C) == 1) res = min(res, phi / d);
            }
        printf("Case %d: %lld\n", T ++ , res);
    }
    return 0;
}