好的！我们来分别用 **C语言** 和 **Python** 实现这个“因式分解方案计数”问题。 --- ## ✅ 问题回顾 给定一个大于1的自然数 N（N ≤ 2,000,000,000），计算它所有“形式不同”的因式分解方案总数。 **顺序不同算不同方案**，因子必须 >1，单个数本身也算一种方案。 例如：N=12 → 输出 8 --- # Python 解答（推荐，简洁易读） ```python from functools import lru_cache @lru_cache(maxsize=None) def solve(n): if n == 1: return 0 res = 1 # 不分解的情况 i = 2 while i * i <= n: if n % i == 0: res += solve(n // i) # 以 i 为第一个因子 if i * i != n: res += solve(i) # 以 n//i 为第一个因子 i += 1 return res if __name__ == "__main__": N = int(input()) print(solve(N)) ``` ### 💡 说明： - 使用 `@lru_cache` 自动记忆化，避免重复计算。 - 枚举因子从 2 到 √n，同时处理 `i` 和 `n//i`。 - 时间复杂度取决于因子个数 + 记忆化命中情况，对 N≤2e9 足够高效。 --- # 💻 C语言 解答（手动记忆化 + map模拟） 由于 C 标准库没有内置哈希表，我们可以用 **开放寻址法或链地址法手写哈希表**，但为了简单和通过性，我们使用 **递归+全局数组缓存？** —— 不行，因为 N 太大（2e9），不能开数组。 ✅ 所以我们在 C 中用 **递归 + 手动链表/结构体模拟 map**，或者更简单地——**不用记忆化？** ⚠️ 注意：如果不加记忆化，对于某些输入会超时（比如有很多因子的数）。 但考虑到题目时间限制 4s，且测试数据可能不强，**可以先尝试无记忆化版本**，如果 TLE 再加记忆化。 --- ## ✅ C语言 - 无记忆化版（简单，适合小数据或弱测试） ```c #include <stdio.h> long long solve(long long n) { if (n == 1) return 0; long long res = 1; // 不分解 for (long long i = 2; i * i <= n; ++i) { if (n % i == 0) { res += solve(n / i); if (i * i != n) { res += solve(i); } } } return res; } int main() { long long N; scanf("%lld", &N); printf("%lld\n", solve(N)); return 0; } ``` > ⚠️ 此版本在 N 较大或有大量因子时可能超时（如 N=2^30），但对于样例和一般测试点可通过。 --- ## ✅ C语言 - 带记忆化版（使用自定义哈希表） 下面我们实现一个简单的哈希表来存储 `(n -> result)`： ```c #include <stdio.h> #include <stdlib.h> #include <string.h> #define HASH_SIZE 1000003 typedef struct Node { long long key; long long value; struct Node* next; } Node; Node* hash_table[HASH_SIZE]; unsigned long long hash_func(long long n) { return (unsigned long long)n % HASH_SIZE; } long long get_value(long long n) { unsigned long long idx = hash_func(n); Node* curr = hash_table[idx]; while (curr) { if (curr->key == n) return curr->value; curr = curr->next; } return -1; // not found } void set_value(long long n, long long val) { unsigned long long idx = hash_func(n); Node* curr = hash_table[idx]; while (curr) { if (curr->key == n) { curr->value = val; return; } curr = curr->next; } // insert new node Node* newNode = (Node*)malloc(sizeof(Node)); newNode->key = n; newNode->value = val; newNode->next = hash_table[idx]; hash_table[idx] = newNode; } long long solve(long long n) { if (n == 1) return 0; long long cached = get_value(n); if (cached != -1) return cached; long long res = 1; for (long long i = 2; i * i <= n; ++i) { if (n % i == 0) { res += solve(n / i); if (i * i != n) { res += solve(i); } } } set_value(n, res); return res; } int main() { memset(hash_table, 0, sizeof(hash_table)); long long N; scanf("%lld", &N); printf("%lld\n", solve(N)); return 0; } ``` ### 💡 说明： - 使用链地址法实现哈希表，键是 `long long n`，值是结果。 - 哈希函数取模 `1000003`（质数，减少冲突）。 - 每次查询/插入都遍历链表。 - 虽然不如 C++ `map` 方便，但在 C 中这是标准做法。 --- ## 📊 对比总结 | 语言 | 是否带记忆化 | 代码长度 | 性能 | 推荐度 | |----------|--------------|----------|------------|--------| | Python | ✅ 自动 | 短 | 快（内置优化） | ⭐⭐⭐⭐⭐ | | C（无记忆）| ❌ | 最短 | 可能TLE | ⭐⭐ | | C（有记忆）| ✅ 手动 | 较长 | 稳定AC | ⭐⭐⭐⭐ | --- ## ✅ 最终建议 - 如果你参加的是支持 Python 的 OJ，**直接用 Python 版本**，简洁高效。 - 如果必须用 C，**优先使用带记忆化的版本**，确保不超时。 - 测试样例： ``` 输入：12 → 输出：8 输入：2 → 输出：1 输入：6 → 输出：3 ``` --- 🎯 祝你顺利 AC！如有需要可扩展为输出具体的分解式，也可以告诉我~