UVa 13085 Forming Teams

题目描述你正在管理一家大型跨国公司手头有许多项目。公司现有N NN名员工每名员工有唯一编号1 11到N NN。你要从这些员工中组建非空的团队集合要求所有团队大小相等每个团队负责一个独特的项目并且每名员工恰好属于一个团队。你的任务是计算形成这样的团队集合的方案数。两个方案视为不同如果团队的数量或大小不同或者存在一对员工在一种方案中属于同一个团队而在另一种方案中属于不同的团队。输入格式第一行包含一个整数T TT1 ≤ T ≤ 5000 1 \le T \le 50001≤T≤5000表示测试用例数。接下来T TT行每行一个整数N NN1 ≤ N ≤ 10 6 1 \le N \le 10^61≤N≤106。输出格式对每个测试用例输出Case x:后跟方案数结果对10 9 7 10^971097取模。样例输入3 1 3 10输出Case 1: 1 Case 2: 2 Case 3: 1073题目分析设团队大小为k kk1 ≤ k ≤ N 1 \le k \le N1≤k≤N则团队数量m N / k m N / kmN/k必须为整数。将N NN个不同员工分成m mm个大小均为k kk的无序团队团队之间没有顺序因为交换两个团队不改变任何两人的同队关系方案数为N ! ( k ! ) m ⋅ m ! \frac{N!}{(k!)^m \cdot m!}(k!)m⋅m!N!​总答案为所有满足k ∣ N k \mid Nk∣N的k kk的上述项之和。例如N 10 N10N10k 1 k1k110 ! / ( 1 ! 10 ⋅ 10 ! ) 1 10!/(1!^{10}\cdot 10!) 110!/(1!10⋅10!)1k 2 k2k210 ! / ( 2 ! 5 ⋅ 5 ! ) 945 10!/(2!^5\cdot 5!) 94510!/(2!5⋅5!)945k 5 k5k510 ! / ( 5 ! 2 ⋅ 2 ! ) 126 10!/(5!^2\cdot 2!) 12610!/(5!2⋅2!)126k 10 k10k101 11总和1 945 126 1 1073 194512611073194512611073与样例一致。本题难点在于N NN最大可达10 6 10^6106T TT可达5000 50005000若对每个测试用例直接枚举所有约数并计算阶乘和逆元预处理阶乘后每个约数的计算需要O ( log ⁡ M O D ) O(\log MOD)O(logMOD)的快速幂用于( k ! ) − m (k!)^{-m}(k!)−m但约数个数很少N ≤ 10 6 N \le 10^6N≤106时约数个数最多约240 240240个因此总复杂度可接受。关键在于正确预处理阶乘及其逆元并快速计算幂。解题思路预处理阶乘与逆元由于N NN最大为10 6 10^6106我们可以预处理0 ! 0!0!到N ! N!N!模10 9 7 10^971097的值以及对应的逆元。阶乘数组fact[i] i! mod MOD。逆元数组invfact[i] (i!)^{-1} mod MOD可通过费马小定理计算invfact[MAXN] fact[MAXN]^{MOD-2} mod MOD然后从后往前递推invfact[i-1] invfact[i] * i mod MOD。枚举约数对于每个N NN枚举所有约数k kk作为团队大小。枚举到N \sqrt{N}N​即可同时处理成对出现的约数d dd和N / d N/dN/d。对每个约数k kk令m N / k m N/kmN/k计算term fact [ N ] × ( invfact [ k ] ) m × invfact [ m ] ( m o d M O D ) \textit{term} \textit{fact}[N] \times (\textit{invfact}[k])^m \times \textit{invfact}[m] \pmod{MOD}termfact[N]×(invfact[k])m×invfact[m](modMOD)其中( invfact [ k ] ) m (\textit{invfact}[k])^m(invfact[k])m通过快速幂计算。累加所有项的和对M O D MODMOD取模即为答案。正确性说明公式N ! ( k ! ) m ⋅ m ! \frac{N!}{(k!)^m \cdot m!}(k!)m⋅m!N!​是组合计数的标准结果先给N NN个不同的人排成一列N ! N!N!种然后每k kk个一组顺序划分成m mm组但组内顺序无关除以( k ! ) m (k!)^m(k!)m且组间顺序无关除以m ! m!m!。由于团队是“非空”的k ≥ 1 k \ge 1k≥1且m ≥ 1 m \ge 1m≥1。枚举所有k ∣ N k \mid Nk∣N恰好覆盖所有可能的团队大小因此总和即为所求。复杂度分析预处理阶乘及其逆元O ( MAXN ) O(\text{MAXN})O(MAXN)其中MAXN 10 6 \text{MAXN}10^6MAXN106。每个测试用例枚举约数O ( N ) O(\sqrt{N})O(N​)最坏约10 3 10^3103次循环T 5000 T5000T5000时总循环约5 × 10 6 5 \times 10^65×106次每次可能调用快速幂O ( log ⁡ m ) O(\log m)O(logm)但m ≤ N m \le Nm≤Nlog ⁡ N ≤ 20 \log N \le 20logN≤20总运算量在可接受范围内约10 8 10^8108次操作。空间复杂度O ( MAXN ) O(\text{MAXN})O(MAXN)。代码实现// Forming Teams// UVa ID: 13085// Verdict: Accepted// Submission Date: 2026-07-12// UVa Run Time: 0.020s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;typedeflonglongll;constintMAXN1000000;constll MOD1000000007LL;ll fact[MAXN5],invfact[MAXN5];llmodPow(ll a,ll b){ll res1;a%MOD;while(b){if(b1)resres*a%MOD;aa*a%MOD;b1;}returnres;}intmain(){fact[0]1;for(inti1;iMAXN;i)fact[i]fact[i-1]*i%MOD;invfact[MAXN]modPow(fact[MAXN],MOD-2);for(intiMAXN;i1;--i)invfact[i-1]invfact[i]*i%MOD;intT;scanf(%d,T);for(inttc1;tcT;tc){intN;scanf(%d,N);ll ans0;for(intk1;k*kN;k){if(N%k0){intd1k,d2N/k;intm1N/d1;ll term1fact[N]*modPow(invfact[d1],m1)%MOD*invfact[m1]%MOD;ans(ansterm1)%MOD;if(d2!d1){intm2N/d2;ll term2fact[N]*modPow(invfact[d2],m2)%MOD*invfact[m2]%MOD;ans(ansterm2)%MOD;}}}printf(Case %d: %lld\n,tc,ans);}return0;}总结本题的核心在于将组合计数问题转化为对约数的枚举并利用预处理阶乘及其逆元来快速计算每个约数对应的组合数。关键技巧是使用模逆元处理除法避免浮点运算。利用费马小定理求阶乘逆元提高效率。枚举约数时只到平方根同时处理成对的约数减少循环次数。这类问题通常需要扎实的组合数学基础和模运算技巧适用于N NN较大但约数个数有限的场景。