美文网首页
求因子个数

求因子个数

作者: A黄橙橙 | 来源:发表于2018-03-28 01:18 被阅读0次

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

在此仅贴出一题 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;
}

相关文章

  • 求因子个数

    求因子个数主要用到了 约数个数定理。即个数为数字的 素因子 幂加一 的 积。 在此仅贴出一题 UVA10375。题...

  • Sherlock and Divisors

    题目大意: 给定一个数N,求N的因子中能被2整除的个数。算法: 循环1N,找出每个因子看是否能被整除,复杂度O(N...

  • 完数

    1.问题描述 求某一范围内完数的个数如果一个数等于它的因子之和,则称该数为完数(或完全数)。例如,6的因子为1,2...

  • 数论 欧拉函数

    欧拉函数在解题的作用在于求一个数的质因子的个数,例如φ(24)=8,因为1, 5, 7, 11, 13, 17, ...

  • 牛客网Wannafly挑战赛25 A题

    题目大意 题目链接给你n,p两个数,求n的阶乘中p做为因子出现的个数 分析 如果p为质数的话,很容易求出p出现的次...

  • 黑盒测试用例设计之正交实验法

    一、正交表的描述 因素数:条件因子的个数 水平数:条件因子取值的个数,取所有条件因子中取得值数目最大的那个。 根据...

  • 因子分析常见问题汇总,你想知道的都在这里

    本文以SPSSAU系统为例,针对因子分析的常见问题进行汇总说明。 ①问题一:提取因子个数 提取因子的个数是一个综合...

  • 求质数因子

    题目描述功能:输入一个正整数,按照从小到大的顺序输出它的所有质因子(如180的质因子为2 2 3 3 5 )最后一...

  • python  求1000以内的完全数

    题目 :求1000以内的完全数(如果一个数恰好等于它的因子之和,则称该数为“完全数”,又称完美数或完备数。例如:第...

  • A1096 Consecutive Factors (20分)

    /*题意:1、找出连续的因子,最多的个数,然后因子大小要最小输入:输入一个数字,最大是int的最大输出:输出连续依...

网友评论

      本文标题:求因子个数

      本文链接:https://www.haomeiwen.com/subject/ifiecftx.html