求因子个数

求因子个数主要用到了 约数个数定理。
即个数为数字的 素因子 幂加一 的 积。

在此仅贴出一题 UVA10375。
题意：给你四个数p,q,r,s。让你求C(p,q)/C(r,s)的值。
分析：这可是组合数，范围是1e4，C(1e4,5e3)肯定已经超出long long，但是题目保证了输出1e6，所以一定是有别的方法。通过观察我们组合数公式，非常容易发现其实其中有非常多约分的数字。所以目前问题就转变成了如何把这些数字变成其素因子的积。

//获得素数
void Prim()
{
    for(int i=2;i<maxn;i++){
        if(prim[i]) continue;
        for(int j=i*2;j<maxn;j+=i){
            prim[j]=1;
        }
    }
    int pos=0;
    for(int i=2;i<maxn;i++){
        if(!prim[i]){
            prim[pos++]=i;
        }
    }
}
//important
void getFactor(int p,int v){
    int pos=0;
    while(p!=1){
        while(p%prim[pos]==0){
            factor[pos]+=v;
            p/=prim[pos];
            max_i=max(max_i,pos);
        }
        pos++;
    }
}

//组合数为阶乘
void initFactor(int p,int v){
    for(int i=1;i<=p;i++){
        getFactor(i,v);
    }
}

CodeChef-AMR16C
这是也是一道求因子个数的题。
题意：给你一个数字，如果该数字的因子个数是否奇素数。
分析：数字达到了1e12，直接算肯定就会超时，所以就要用到一个技巧，首先一个数的因子个数想要为奇数，就必须是一个平方数，也就是说，我们可以通过对该数开平方根，来节约时间。

ll cal(int x)
{
    ll ans=1;
    for(int i=2;i*i<=x;i++){
        ll cnt=0;
        while(x%i==0){
            x/=i;
            cnt++;
        }
        ans*=(2*cnt+1);
    }
    if(x!=1) ans*=3;
    return ans;   
}

我们直接用x%i来代替素数prim[i]这样是可以的，原理类似于埃式筛法，这样运行时间大概是600ms。
如果优化一下，用上类似上一题的 获得素数 ，那么运行时间仅需要180ms

ll cal(int x)
{
    ll ans=1;
    for(int i=0;prim[i]*prim[i]<=x;i++){
        ll cnt=0;
        while(x%prim[i]==0){
            x/=prim[i];
            cnt++;
        }
        ans*=(2*cnt+1);
    }
    if(x!=1) ans*=3;
    return ans;
}