long long fact_small(int n) {
return (n <= 1) ? 1 : n * fact_small(n - 1);
}
12! = 479001600 仍在 32 位有符號範圍內;13! 溢出。
數組 a[0] 存長度,a[1] 存個位,a[2] 存十位... (低位在前)。
void multiply(int a[], int b) { // a *= b
int carry = 0;
for (int i = 1; i <= a[0]; ++i) {
int prod = a[i] * b + carry;
a[i] = prod % 10;
carry = prod / 10;
}
while (carry) {
a[++a[0]] = carry % 10;
carry /= 10;
}
}
void big_factorial(int n, int result[]) {
result[0] = 1; result[1] = 1; // 1! = 1
for (int i = 2; i <= n; ++i) multiply(result, i);
}
void print_big(const int a[]) {
for (int i = a[0]; i >= 1; --i) std::cout << a[i];
std::cout << '\n';
}
核心觀察:末尾 0 來自因子 2×5,2 的個數遠超 5。去除所有因子 5 並同步移除等量因子 2,剩餘乘積模 10 即為答案。
規律:5 ≡ 8 (mod 10) 當配對因子 2 時,故可將每個因子 5 視為 8 參與乘積。因子 5 的個數模 4 循環 (2,6,8,4)。
int last_nonzero_digit(int n) {
static const int res[5][4] = {
{0,0,0,0},
{2,6,8,4}, // 1 個因子5
{4,2,6,8}, // 2 個
{6,8,4,2}, // 3 個
{8,4,2,6} // 4 個
};
int nonzero = 1, five = 0;
for (int i = 2; i <= n; ++i) {
int t = i;
while (t % 5 == 0) { t /= 5; five = (five + 1) % 4; }
while (t % 2 == 0 && five) { t /= 2; five = (five + 3) % 4; } // 移除配對的2
nonzero = (nonzero * t) % 10;
if (five) nonzero = res[nonzero/2][five]; // nonzero 為偶數
}
return nonzero;
}
等價於統計 1~n 中因子 5 的總個數:
int trailing_zeros(int n) {
int cnt = 0;
while (n) { n /= 5; cnt += n; }
return cnt;
}
用 double 維持科學記數法有效數字:
int second_digit(int n) {
double val = 1;
for (int i = 2; i <= n; ++i) {
val *= i;
while (val >= 100) val /= 10; // 保持兩位有效數字
}
return static_cast<int>(val) % 10;
}
素因子分解法:對 m 的每個質因子 p,比較 n! 中 p 的指數 (Legendre 公式) 是否 ≥ m 中的指數。
bool divides_factorial(int m, int n) {
if (m == 0) return false;
if (n >= m) return true;
int mm = m;
for (int p = 2; p * p <= mm; ++p) {
if (mm % p) continue;
int cnt_m = 0;
while (mm % p == 0) { mm /= p; ++cnt_m; }
int cnt_n = 0, t = n;
while (t) { t /= p; cnt_n += t; }
if (cnt_n < cnt_m) return false;
}
if (mm > 1) { // 剩餘大質因子
int cnt_n = 0, t = n;
while (t) { t /= mm; cnt_n += t; }
if (cnt_n < 1) return false;
}
return true;
}
可用數字僅 10 個,DFS 全搜索即可 (2^10 = 1024 種組合)。
bool can_sum_factorial(int N) {
int fact[10]; fact[0] = 1;
for (int i = 1; i < 10; ++i) fact[i] = fact[i-1] * i;
std::vector<bool> reachable(3628800 + 1, false); // 9! = 362880
std::function<void(int,int)> dfs = [&](int idx, int sum) {
if (idx == 10) { reachable[sum] = true; return; }
dfs(idx+1, sum);
dfs(idx+1, sum + fact[idx]);
};
dfs(0, 0);
return N < reachable.size() && reachable[N];
}
e_p(n!) = Σ floor(n/p^k)。BigInteger 類 (或用 boost::multiprecision::cpp_int),避免重複造輪子。