天天看點
傳回

AcWing 202. 最幸運的數字

​​題目傳送門​​

一、總結

用到了 \(6\)個知識點：

1. 由 \(x\) 個 \(y\) 組成的數的公式是\(\large \displaystyle y*\frac{10^x-1}{9}\)。比如 \(88888888\)這種數。

證明：

\(\large \displaystyle \underbrace{8...8}_{x}=8 \times \underbrace{1...1}_{x}=8 \times \frac{9...9}{9}=8 \times \frac{10^x-1}{9}\)

2. 歐拉定理

若 \(a, n\)為正整數，且\(a,n\)互質 ，則 $$\large a^{φ(n)}≡1(mod \ n)$$

其中\(\phi(n)\)指歐拉函數值。如果\(a,n\)不互質，則方程無解。

3. 歐拉定理推論

若正整數\(a,n\)互質，則滿足\(a^x \equiv 1 \ (mod \ n)\)的最小正整數 \(x_0\)是\(\phi(n)\)的約數。

4. 快速幂

// 原生快速幂 (a^k)%p
LL qmi(LL a, LL k, LL p) {
    LL res = 1;
    while (k) {
        if (k & 1) res = res * a % p;
        k >>= 1;
        a =  a * a % p;
    }
    return res;
}

5. 快速幂+龜速乘

當模數\(>1e9\)的時候，在相乘的時候爆\(long\) \(long\)了。

參考網址：​

//龜速乘
//時間複雜度：logn,乘法本來是O(1),這麼幹成了O(logN)了。
//優點：可以防止在LL*LL % MOD 過程中爆掉LL，可以将乘法分解成多步加法，在加的過程中不斷取模。
LL qmul(LL a, LL k, LL b) {
    LL res = 0;
    while (k) {
        if (k & 1) res = (res + a) % b;
        a = (a + a) % b;
        k >>= 1;
    }
    return res;
}

//快速幂+龜速乘
LL qmi(LL a, LL k, LL b) {
    LL res = 1;
    while (k) {
        if (k & 1) res = qmul(res, a, b); //調用龜速乘,原因是本題的資料範圍是2*1e9,直接乘會爆掉LL，需要一路乘來一路取模
        a = qmul(a, a, b);
        k >>= 1;
    }
    return res;
}

6. INT128配合快速幂

//下面的辦法可以用來測試編譯器是不是支援 LLL
typedef __int128 LLL;

//快速幂+  LLL
LL qmi(LL a, LL k, LL b) {
    LL res = 1;
    while (k) {
        if (k & 1) res = (LLL)res * a % b;
        a = (LLL)a * a % b;
        k >>= 1;
    }
    return res;
}

二、推導過程

題目實際上要我們求一個最小的正整數 \(x\)，滿足 \(\large \displaystyle L|8*\frac{10^x-1}{9}\)

我們來轉化一下這個限制條件：

\[\large \displaystyle \Leftrightarrow 9*L | 8(10^x-1)

\]

令\(\large \displaystyle d=gcd(L,8)\),那麼約分:

\[\large \displaystyle \Leftrightarrow \frac{9*L}{d} | 10^x-1 \ \ \ \ ①

\]

\[\large \displaystyle \Leftrightarrow 10^x-1 \equiv 0 \ (mod \ \frac{9*L}{d})

\]

\[\large \displaystyle \Leftrightarrow 10^x \equiv 1 \ (mod \ \frac{9*L}{d})

\]

設\(\large \displaystyle p=\frac{9*L}{d}\)

即:

\[\large \displaystyle \Leftrightarrow 10^x \equiv 1 \ (mod \ p)

\]

最終變成求解滿足 \(\large \displaystyle 10^x≡1(mod \ p)\) 的最小正整數 \(x\)

注釋 ① :(一開始我看不懂這一步，解釋一下\(qwq\))
  • $\large \displaystyle gcd(8,9)=1 \Rightarrow d=gcd(9L,8)=gcd(8,L) $ (參考黃海整理的最大公約數性質\(4\))

  • \(d\)既然是兩個數的最大公約數，那麼兩個數都除以\(d\)後，得到的兩個新數，必須互質 (這是最大公約數的定義)

    即：\(\large \displaystyle \frac{9*L}{d}\)與\(\large \displaystyle \frac{8}{d}\)是互質的,而\(\large \displaystyle 10^x-1\)還想是\(\large \displaystyle \frac{9*L}{d}\)的整數倍

    是以 \(\large \displaystyle \frac{9*L}{d}\)一定是\(\large \displaystyle 10^x-1\)的因數，是以\(\large \displaystyle \Leftrightarrow \frac{9*L}{d} | 10^x-1\)

三、歐拉定理

歐拉定理: \(\large \displaystyle a^{φ(n)}≡1(mod \ n)\)(其中\(\large \displaystyle gcd(a,n)=1\))

這裡的形式有點像歐拉定理，\(\large a^{\phi(c)}\equiv 1 (mod \ p)\)但是歐拉定理隻是說\(\large φ(n)\)是一個解，但不能保證 \(\large φ(n)\) 是滿足等式的最小正整數!

四、實作代碼(快速幂+龜速乘) 

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

//最大公約數
int gcd(int a, int b) {
    if (b == 0) return a;
    return b ? a : gcd(b, a % b);
}

//龜速乘
LL qmul(LL a, LL k, LL b) {
    LL res = 0;
    while (k) {
        if (k & 1) res = (res + a) % b;
        a = (a + a) % b;
        k >>= 1;
    }
    return res;
}

//快速幂+龜速乘
LL qmi(LL a, LL k, LL b) {
    LL res = 1;
    while (k) {
        if (k & 1) res = qmul(res, a, b);
        a = qmul(a, a, b);
        k >>= 1;
    }
    return res;
}

/**
 * 功能：歐拉函數
 * @param x
 * @return
 */
LL get_euler(LL x) {
    LL res = x;
    for (int i = 2; i <= x / i; i++)
        if (x % i == 0) {
            res = res / i * (i - 1);
            while (x % i == 0) x /= i;
        }
    if (x > 1) res = res / x * (x - 1);
    return res;
}

int main() {
    int T = 1; //準備輸出Case i
    LL L;
    while (cin >> L, L) {
        int d = gcd(L, 8);     // L和8的最大公約數 gcd(8,L)
        LL p = 9 * L / d;      // 公式推導得到的p
        LL phi = get_euler(p); // 單個數字p的歐拉函數值φ(p)
        LL res = LONG_LONG_MAX; //預求最小先設最大

        if (gcd(p, 10) > 1) //判斷p和10是否互質,不互質:方程無解，輸出0
            res = 0;
        else {
            for (LL d = 1; d * d <= phi; d++) //枚舉φ(p)的每個小約數,到sqrt(φ(p))
                if (phi % d == 0) {           //如果d是約數,那麼其實我們一次發現了兩個約數： d 和 phi/d
                    //這裡與原來的質因子分解有一點點不同，因為那個隻要枚舉小于sqrt(n)的，并且 n %d==0,
                    //就一定是它的小質數因子，本題不是這個意思。
                    //本題的目标是找出所有因子，注意，不是小因子。
                    //因為，小因子不見得能是方程的解，大因子不見得不是方程的解！！
                    //對于它們，都有機會成為答案，需要全部讨論到！然後PK最小值即可！
                    //如果這個約數d，滿足 10 ^ d ≡ 1 (mod p) ，那麼它有機會成為答案
                    if (qmi(10, d, p) == 1) res = min(res, d);             //小約數
                    //如果這個約數phi/d，滿足 10 ^ (phi/d) ≡ 1 (mod p) ，那麼它有機會成為答案
                    if (qmi(10, phi / d, p) == 1) res = min(res, phi / d); //大約數
                }
        }
        //輸出
        printf("Case %d: %lld\n", T++, res);
    }
    return 0;
}

五、快速幂+__int128 

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

//下面的辦法可以用來測試編譯器是不是支援 LLL
typedef unsigned __int128 LLL;

//最大公約數
int gcd(int a, int b) {
    if (b == 0) return a;
    return b ? a : gcd(b, a % b);
}

//快速幂+  LLL
LL qmi(LL a, LL k, LL b) {
    LL res = 1;
    while (k) {
        if (k & 1) res = (LLL)res * a % b;
        a = (LLL)a * a % b;
        k >>= 1;
    }
    return res;
}

/**
 * 功能：歐拉函數
 * @param x
 * @return
 */
LL get_euler(LL x) {
    LL res = x;
    for (int i = 2; i <= x / i; i++)
        if (x % i == 0) {
            res = res / i * (i - 1);
            while (x % i == 0) x /= i;
        }
    if (x > 1) res = res / x * (x - 1);
    return res;
}

int main() {
    int T = 1; //準備輸出Case i
    LL L;
    while (cin >> L, L) {
        int d = gcd(L, 8);      // L和8的最大公約數 gcd(8,L)
        LL p = 9 * L / d;       // 公式推導得到的p
        LL phi = get_euler(p);  // 單個數字p的歐拉函數值φ(p)
        LL res = LONG_LONG_MAX; //預求最小先設最大

        if (gcd(p, 10) > 1) //判斷p和10是否互質,不互質:方程無解，輸出0
            res = 0;
        else {
            for (LL d = 1; d * d <= phi; d++) //枚舉φ(p)的每個小約數,到sqrt(φ(p))
                if (phi % d == 0) {           //如果d是約數,那麼其實我們一次發現了兩個約數： d 和 phi/d
                    //這裡與原來的質因子分解有一點點不同，因為那個隻要枚舉小于sqrt(n)的，并且 n %d==0,
                    //就一定是它的小質數因子，本題不是這個意思。
                    //本題的目标是找出所有因子，注意，不是小因子。
                    //因為，小因子不見得能是方程的解，大因子不見得不是方程的解！！
                    //對于它們，都有機會成為答案，需要全部讨論到！然後PK最小值即可！
                    //如果這個約數d，滿足 10 ^ d ≡ 1 (mod p) ，那麼它有機會成為答案
                    if (qmi(10, d, p) == 1) res = min(res, d); //小約數
                    //如果這個約數phi/d，滿足 10 ^ (phi/d) ≡ 1 (mod p) ，那麼它有機會成為答案
                    if (qmi(10, phi / d, p) == 1) res = min(res, phi / d); //大約數
                }
        }
        //輸出
        printf("Case %d: %lld\n", T++, res);
    }
    return 0;
}
快速幂 最大公約數 最小值
上一篇: MGR限制說明
下一篇: mysql mgr問題_mysql MGR常見問題大全

繼續閱讀