标签归档:欧拉定理

POJ 3696 -The Luckiest number


题目链接:POJ 3696

题意:给定一个正整数\(L\), \(L \le 2*10^9\). 问至少多少个\(8\)连在一起组成的正整数是\(L\)的倍数?

solution:
\(x\)个\(8\)连在一起组成的正整数可写作\(8(10^x-1)/9\). 题目就是要求出一个最小的\(x\),满足\(L| \frac{8(10^x-1)}{9} \).

设 \(d = gcd(L,8)\),

有\(9L | 8(10^x-1) \Leftrightarrow \frac{9L}{d}|(10^x-1) \Leftrightarrow 10^x \equiv 1 \pmod {\frac{9L}{d}} \)

引理:若正整数\(a,n\)互质,则满足\(a^x\equiv 1 \pmod n\)的最小正整数\(x_0\)是\(\varphi(n)\)的约数(可通过反证法证明)

根据以上,只需求出欧拉函数\(\varphi(\frac{9L}{d})\), 枚举它的所有约数,用快速幂逐一检查是否满足条件即可。

code:

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <string>
#include <vector>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

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

ll getPhi(ll n) {
  ll ans = n;
  for (ll i = 2; i <= sqrt(n); ++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;
}

ll mul(ll mod, ll a, ll b) {
  ll res = 0;
  while (b) {
    if (b & 1) {
      res = (res + a) % mod;
    }
    a = (a << 1) % mod;
    b >>= 1;
  }
  return res;
}

ll quickpow(ll mod, ll m, ll n) {
  ll res = 1;
  while (n) {
    if (n & 1) res = mul(mod, res, m);
    m = mul(mod, m, m);  // 注意:直接乘会溢出!
    n >>= 1;
  }
  return res;
}

int main() {
  ll n;
  int kase = 0;
  while (cin >> n && n) {
    ll t = n / gcd(n, 8) * 9;
    ll p = getPhi(t);
    int flag = 0;
    for (ll i = 1; i <= sqrt(p); ++i) {
      if (p % i == 0) {
        if (quickpow(t, 10, i) == 1) {
          printf("Case %d: %lldn", ++kase, i);
          flag = 1;
          break;
        }
      }
    }
    if (!flag) {
      for (ll i = sqrt(p); i >= 1; --i) {
        if (p % i == 0) {
          if (quickpow(t, 10, p / i) == 1) {
            printf("Case %d: %lldn", ++kase, p / i);
            flag = 1;
            break;
          }
        }
      }
    }
    if (!flag) printf("Case %d: %dn", ++kase, 0);
  }
  return 0;
}