Acwing 4083. 最大公约数 方法一：枚举所有数，统计其倍数在输入中的次数
方法二：统计输入数的质因子个数，选最大的一个		 O(NlogN)
O(Nsqrt(N))
131. 绝对值表达式的最大值 绝对值转换 + 枚举
AcWing 1295. X的因子链 筛法求素数 + 多重集合全排列
AcWing 4486. 数字操作 分解质因数 + 对数
6115. 统计理想数组的数目 数论+ 组合数学
1735. 生成乘积数组的方案数 类似于6115的题目

一道综合题

AcWing 202. 最幸运的数字
8 是中国的幸运数字，如果一个数字的每一位都由 8 构成则该数字被称作是幸运数字。
现在给定一个正整数 L，请问至少多少个 8 连在一起组成的正整数（即最小幸运数字）是 L 的倍数。
输入格式
输入包含多组测试用例。
每组测试用例占一行，包含一个整数 LL。
当输入用例 L=0 时，表示输入终止，该用例无需处理。
输出格式
每组测试用例输出结果占一行。
结果为 Case i:+一个整数 N，N 代表满足条件的最小幸运数字的位数。
如果满足条件的幸运数字不存在，则 N=0。
数据范围
1≤L≤2×109
输入样例：
8 11 16 0
输出样例：
Case 1: 1
Case 2: 2
Case 3: 0

思路：
第一步：如何表示连续x位8所代表的数字
8...88 = 8 * 1....11 = 8 * 9....99 / 9 = 8 * (10x - 1) / 9
第二步：列式化简
L | 8 * (10x - 1) / 9 -> 9L | 8 * (10x - 1)
若d1 = gcd(9L, 8) = gcd(L, 8)则有9L / d1 | 8 / d1 * (10x - 1)，又因为gcd(9L / d1, 8) = 1，故9L / d1 | (10x - 1) -> 10x = 1 (mod 9L / d1)
第三步：求解x
令c = 9L / d1，有解的充要条件是gcd(c, 10) = 1
第四步：若有解，解是什么
解是10关于c的最小次数，并且有x | euler(c)
故可用试除法求出euler(c)，然后用试除法遍历c的所有约数，用快速幂 + 龟速乘找到最小的满足条件的x :::danger 本题会爆LL，离谱 :::

  1. static int l;
  2. static void solve() {
  3.     int T = 1;
  4.     while (true) {
  5.         l = ni();
  6.         if (l == 0) break;
  7.         long d = gcd(l, 8);
  8.         long c = 9L * l / d;
  9.         long d2 = gcd(10, c);
  10.         if (d2 != 1) {
  11.             out.println(String.format("Case %d: %d", T++, 0));
  12.         } else {
  13.             long euler = getEuler(c);
  14.             long res = euler;
  15.             for (int i = 1; i <= euler / i; i++) {
  16.                 if (euler % i == 0) {
  17.                     long v = qmi(10, i, c);
  18.                     if (v == 1)
  19.                         res = Math.min(res, i);
  21.                     if (euler / i != i) {
  22.                         v = qmi(10, euler / i, c);
  23.                         if (v == 1)
  24.                             res = Math.min(res, euler / i);
  25.                     }
  26.                 }
  27.             }
  29.             out.println(String.format("Case %d: %d", T++, res));
  30.         }
  31.     }
  32. }
  34. static long qmi(long a, long b, long c) {
  35.     long res = 1;
  36.     a %= c;
  37.     while (b > 0) {
  38.         if ((b & 1) == 1)
  39.             res = qmul(res, a, c);
  40.         b >>= 1;
  41.         a = qmul(a, a, c);
  42.     }
  43.     return res;
  44. }
  46. static long qmul(long a, long b, long c) {
  47.     long res = 0;
  48.     while (b > 0) {
  49.         if ((b & 1) == 1)
  50.             res = (res + a) % c;
  51.         b >>= 1;
  52.         a = (a + a) % c;
  53.     }
  54.     return res;
  55. }
  57. static long getEuler(long c) {
  58.     long res = c;
  59.     for (int i = 2; i <= c / i; i++) {
  60.         if (c % i == 0) {
  61.             while (c % i == 0) {
  62.                 c /= i;
  63.             }
  64.             res = res / i * (i - 1);
  65.         }
  66.     }
  67.     if (c > 1) res = res / c * (c - 1);
  68.     return res;
  69. }
  71. static long gcd(long x, long y) {
  72.     return y == 0 ? x : gcd(y, x % y);
  73. }