链接:

https://www.acwing.com/problem/content/204/

题意:

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

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

思路:

求出式子8(10^x-1)/9为8组成的正整数.

另其为G, 有L|G, 两边同乘9,9L | 8(10^x-1),为了去掉右边的8, 令右边为变为原来的1/8, 左边变为原来的gcd(L, 8)倍.

令d = gcd(8, L), 9L/d 与 8/L互质, 因为9L/d | 8/d(10^x-1), 所以有9L/d | (10^x-1).

剩下就是同余, 10^x = 1 (mod 9L/d)假装是同余符号.

根据欧拉定理, x为fai(9*L/d) 的约数.枚举再暴力判断.

代码:

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

LL n;

LL Pow(LL a, LL b, LL mod)

{

    LL res = 1;

    while (b)

    {

        if (b&1)

            res = (res*a)%mod;

        a = (a*a)%mod;

        b >>= 1;

    }

    return res;

}

LL Euler(LL x)

{

    LL res = x;

    for (int i = 2;i <= x;i++)

    {

        if (x%i == 0)

        {

            while (x % i == 0)

                x /= i;

            res = res/i*(i - 1);

        }

    }

    if (x > 1)

        res = res/x*(x-1);

    return res;

}

LL Solve(int cnt, LL mod)

{

    LL res = 1e18;

    for (LL i = 1;i*i <= cnt;i++)

    {

        if (cnt%i == 0)

        {

//            cout << i << endl;

            if (Pow(10, i, mod) == 1)

                res = min(res, i);

            if (Pow(10, cnt/i, mod) == 1)

                res = min(res, cnt/i);

        }

    }

    if (res == 1e18)

        return 0;

    return res;

}

int main()

{

    int cnt = 0;

    while (~scanf("%lld", &n) && n)

    {

        LL eul = Euler((9LL*n)/__gcd(8LL, n*9));

//        cout << eul << endl;

        LL res = Solve(eul, (9LL*n)/__gcd(8LL, n*9));

        printf("Case %d: %lld\n", ++cnt, res);

    }

    return 0;

}

巴特西

Acwing-202-最幸运的数字(同余, 欧拉定理)

链接:

题意:

思路:

代码:

最新文章

热门文章