UVa 12619 Just Make A Wish-编程实验室

题目描述

你有一个朋友Po\texttt{Po}Po，他有一个神奇的精灵。精灵每天会告诉Po\texttt{Po}Po一个整数GGG。如果GGG为正数，那么Po\texttt{Po}Po的土地面积会乘以GGG；如果GGG为负数，那么Po\texttt{Po}Po的土地面积会除以∣G∣|G|∣G∣（保证能整除）。初始土地面积为111。每天，你需要计算出当前土地面积对应的“不同矩形”的数量，即面积的正整数因子个数（因为矩形边长必须是正整数，且a×ba \times ba×b与b×ab \times ab×a视为不同，除非a=ba = ba=b）。在DDD天结束后，输出每天因子个数的总和，并对109+710^9+7109+7取模。

输入格式

第一行是测试用例数TTT（T≤10T \le 10T≤10）。
每个测试用例第一行是天数DDD（1≤D≤1061 \le D \le 10^61≤D≤106）。
接下来DDD行，每行一个整数GGG（0<∣G∣≤1060 < |G| \le 10^60<∣G∣≤106）。

输出格式

对于每个测试用例，输出一行Case X: sum，其中XXX是测试用例编号，sumsumsum是DDD天因子个数总和对109+710^9+7109+7取模的结果。

题目分析

问题转化

每天我们需要计算当前面积AAA的正整数因子个数。
设AAA的质因数分解为：
A=p1e1p2e2…pkek A = p_1^{e_1} p_2^{e_2} \dots p_k^{e_k}A=p1e1p2e2…pkek
则AAA的因子个数为：
div_count(A)=∏i=1k(ei+1) \texttt{div\_count}(A) = \prod_{i=1}^k (e_i + 1)div_count(A)=i=1∏k(ei+1)
因为每个质因子pip_ipi的指数可以从000到eie_iei选择，共有ei+1e_i+1ei+1种选择，组合起来就是乘积。

动态维护

如果我们每天重新分解AAA，复杂度会非常高（因为AAA可能极大）。
注意到每天AAA只会乘以或除以一个数∣G∣|G|∣G∣，我们可以动态维护AAA的质因数分解（即每个质因子的指数），并相应地更新因子个数。

更新方法

当乘以xxx时，对xxx分解质因数，对于每个质因子ppp及其指数eee：
- 设ppp原来的指数为old_expold\_expold_exp，新的指数new_exp=old_exp+enew\_exp = old\_exp + enew_exp=old_exp+e。
- 因子个数需要乘以new_exp+1old_exp+1\frac{new\_exp+1}{old\_exp+1}old_exp+1new_exp+1。
当除以xxx时，对xxx分解质因数，对于每个质因子ppp及其指数eee：
- 设ppp原来的指数为old_expold\_expold_exp，新的指数new_exp=old_exp−enew\_exp = old\_exp - enew_exp=old_exp−e。
- 因子个数需要乘以new_exp+1old_exp+1\frac{new\_exp+1}{old\_exp+1}old_exp+1new_exp+1。

由于我们需要对109+710^9+7109+7取模，而模数是质数，因此可以用模逆元来处理除法。

算法步骤

预处理
- 使用线性筛法求出每个数的最小质因子（Least Prime Factor, LPF \texttt{Least Prime Factor, LPF }Least Prime Factor, LPF），以便快速分解∣G∣|G|∣G∣。
- 预处理111到2×1062\times 10^62×106的模逆元（因为指数可能很大，但指数不会超过2×1062\times 10^62×106）。
对每个测试用例
- 初始化一个哈希表expMap存储当前面积的质因子指数，初始为空（面积111时所有指数为000）。
- 初始化因子个数divCount = 1（111的因子个数为111）。
- 初始化总和sumWays = 0。
- 对于每一天的GGG：
  - 计算val=∣G∣val = |G|val=∣G∣。
  - 使用 LPF 快速分解valvalval。
  - 根据GGG的正负，更新expMap和divCount。
  - 将当天的divCount累加到sumWays（取模）。
- 输出结果。

复杂度分析

预处理LPF\texttt{LPF}LPF和逆元：O(MAXlog⁡log⁡MAX)O(MAX \log \log MAX)O(MAXloglogMAX)，其中MAX=2×106MAX = 2\times 10^6MAX=2×106。
每天分解∣G∣|G|∣G∣：O(log⁡∣G∣)O(\log |G|)O(log∣G∣)。
总复杂度：O(T⋅D⋅log⁡∣G∣)O(T \cdot D \cdot \log |G|)O(T⋅D⋅log∣G∣)，在D≤106D \le 10^6D≤106时可接受。

代码实现

// Just Make A Wish// UVa ID: 12619// Verdict: Accepted// Submission Date: 2025-12-17// UVa Run Time: 0.200s//// 版权所有（C）2025，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;typedeflonglongLL;constintMAX=2000005;// 足够大，因为 G 最大 1e6，但面积质因子可能更大constLL MOD=1000000007LL;vector<int>lpf;// 最小质因子 Least Prime Factorvector<LL>inv;// 模逆元// 快速幂取模LLmodPow(LL a,LL b){LL res=1;while(b){if(b&1)res=res*a%MOD;a=a*a%MOD;b>>=1;}returnres;}// 预处理最小质因子和逆元voidinit(){lpf.resize(MAX,0);inv.resize(MAX,0);for(inti=2;i<MAX;i++){if(lpf[i]==0){// i 是质数lpf[i]=i;for(intj=i+i;j<MAX;j+=i){if(lpf[j]==0)lpf[j]=i;}}}// 预处理逆元： inv[x] = x^(-1) mod MODfor(inti=1;i<MAX;i++)inv[i]=modPow(i,MOD-2);}// 分解 x，返回质因子-指数的映射vector<pair<int,int>>factorize(intx){vector<pair<int,int>>res;while(x>1){intp=lpf[x];intcnt=0;while(x%p==0){x/=p;cnt++;}res.push_back({p,cnt});}returnres;}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);init();// 预处理intT;cin>>T;for(intcaseNo=1;caseNo<=T;caseNo++){intD;cin>>D;unordered_map<int,int>expMap;// 当前面积的质因子指数LL divCount=1;// 当前面积的因子个数LL sumWays=0;for(intday=0;day<D;day++){intG;cin>>G;intval=abs(G);vector<pair<int,int>>factors=factorize(val);if(G>0){// 乘以 valfor(auto&pf:factors){intp=pf.first,e=pf.second;intoldExp=expMap[p];intnewExp=oldExp+e;// 更新因子个数：除以(oldExp+1)，乘以(newExp+1)divCount=divCount*inv[oldExp+1]%MOD;divCount=divCount*(newExp+1)%MOD;expMap[p]=newExp;}}else{// 除以 valfor(auto&pf:factors){intp=pf.first,e=pf.second;intoldExp=expMap[p];intnewExp=oldExp-e;divCount=divCount*inv[oldExp+1]%MOD;divCount=divCount*(newExp+1)%MOD;expMap[p]=newExp;}}sumWays=(sumWays+divCount)%MOD;}cout<<"Case "<<caseNo<<": "<<sumWays<<"\n";}return0;}