解题报告 POJ3696 The Luckiest number

题意

给定正整数 L 满足 L\in[2, 10^9]，问至少多少个 8 连起来组成的正整数是 L 的倍数

思路

首先设 x 个 8 连起来，这个数记为 \displaystyle \frac{8(10^x-1)}{9}，题意就是求最小正整数 x 使得 L\mid \displaystyle \frac{8(10^x-1)}{9}。

首先将式子化为 9L\mid 8(10^x – 1)，两边同时约去 d=\gcd(L, 8) 得到 \displaystyle \frac{9L}{d} \mid 10^x – 1

所以原式化为

10^x\equiv 1\pmod{\frac{9L}{d}}

引理

若正整数 a\perp n，则满足 a^x\equiv 1\pmod n 的最小正整数 x_0 为 \varphi(n) 的约数。

使用欧拉定理 a^{\varphi(n)}\equiv 1\pmod n 可以证明

所以设 p = \varphi\left(\displaystyle \frac{9L}{d}\right)，枚举其所有约数 x，符合条件即为答案。

模数可能为 long long，要开快速乘

#include <cstdio>
#include <cmath>
#include <queue>
#include <algorithm>
#define int long long

int gcd(int a, int b)
{
    if (!b) return a;
    return gcd(b, a % b);
}

int phi(int n)
{
    int ans = n, sq = sqrt(n);
    for (int i = 2; i <= sq; ++i)
    {
        if (n % i == 0)
        {
            ans = ans / i * (i - 1);
            while (n % i == 0)
                n /= i;
        }
    }
    if (n > 1)
        ans = ans / n * (n - 1);
    return ans;
}

int mul(int a, int b, int mod)
{
    int ans = 0, x = a;
    b = (b + mod) % mod, a = (a + mod) % mod;
    for (; b; b >>= 1ll)
    {
        if (b & 1ll)
            ans = (ans + x) % mod;
        x = (x << 1) % mod;
    }
    return ans;
}

int ksm(int base, int p, int mod)
{
    int ans = 1;
    base %= mod;
    for (; p; p >>= 1)
    {
        if (p & 1)
            ans = mul(ans, base, mod);
        base = mul(base, base, mod);
    }
    return ans;
}

std::vector<int> fact;

signed main()
{
    int n;
    for (signed kase = 1; ; ++kase)
    {
        scanf("%lld", &n);
        if (!n)
            return 0;
        int d = gcd(n, 8);
        int phip = phi(9 * n / d), sqrtp = sqrt(phip);
        fact.clear();
        for (int i = 2; i <= sqrtp; ++i)
            if (phip % i == 0)
            {
                fact.push_back(i);
                if (phip / i != i)
                    fact.push_back(phip / i);
            }
        std::sort(fact.begin(), fact.end());
        int ans = 0;
        for (int i = 0; i < fact.size(); ++i)
        {
            if (ksm(10, fact[i], 9 * n / d) == 1)
            {
                ans = fact[i];
                break;
            }
        }
        printf("Case %d: %lld\n", kase, ans);
    }
    return 0;
}