求因子个数主要用到了 约数个数定理。
即个数为数字的 素因子 幂加一 的 积。
在此仅贴出一题 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;
}
