乘法溢出及对策

 最近几次碰到乘法溢出，



情况一：
下面是修订后的版本
void dfs(int pos, int lim, int val, int div)
{
    int i,j;
    if(pos>prime[0]||prime[pos]>lim) return;
    int t=prime[pos];
    for(i=1,j=1; i<=lim/t;j++){
        i*=t;
        divisor[val*i]=div*(j+1);
        dfs(pos+1,lim/i,val*i,div*(j+1));
    }
    dfs(pos+1,lim,val,div);
}
原来的版本是for(i=1,j=1; i*t<=lim;j++)，结果i*t溢出变成负数导致divisor[val*i]的下标为负


情况二多一个乘法，导致顾此失彼： LIMIT 是500000，在下面的for循环
for(t=prime[ob.ind];t<=LIM/ob.cur;t*=prime[ob.ind])
t是第4793个质数46349，ob.cur为8，导致t*=prime[ob.ind]会产生乘法溢出（超过2^31-1),其实t<=LIM/ob.cur已经是为了避免乘法溢出的做法，结果还是没有考虑到后面的乘法。
程序运行最终产生了access violation（VC），因为divs[t*ob.cur]的下标出现了一个大负数。

解决的办法：因为这是都不超过int的范围，将相关类型扩展成long long就解决了。当然也可以采用上面的方式。

struct frame{
        int ind,cur,cur_div;
        frame(int i,int c, int d):ind(i),cur(c),cur_div(d){}
    };

void dfs(int ind, int cur, int cur_div)
{
   
    stack st;
    st.push(frame(ind,cur,cur_div));
   
    while(!st.empty()){
        frame ob=st.top();
        st.pop();
        if(ob.ind==prime[0]+1 || ob.cur>LIM/prime[ob.ind]) continue;
        st.push(frame(ob.ind+1,ob.cur,ob.cur_div));
        int t,tot=1;
        for(t=prime[ob.ind];t<=LIM/ob.cur;t*=prime[ob.ind]){
            tot+=t;
            divs[t*ob.cur]=ob.cur_div*tot;
            st.push(frame(ob.ind+1,ob.cur*t,ob.cur_div*tot));
        }
    }
}

最新的情况
要求 prime[i]^p * prime[i+k]^(p+t)<=10^9  prime[i+k]^(p+t)本身可能超过10^9，对数取整也许可以解除所有溢出烦恼，唯一不确定的就是浮点类型精度是损失是否会带来不可接受的误差

p*log10((double)prime[i])+(p+t)*log10((double)prime[i+k])<=9.0