算法竞赛中的一些模板(数论)

1、组合数C(n,m)

long long C(int n,int m)//进行约分操作的版本
{
    if(m<n-m)
    m=n-m;//上面的m始终保持更小
    for(int i=m+1;i<=n;i++)
    ans*=i;
    for(int i=1;i<=n-m;i++)
    ans/=i;

    return ans;
}

2、素数判定
(1)普通版 参数为int n太大时速度很慢

int is_prime(int n)
{
    if(n<=1)
    return 0;
    int m=floor(sqrt(n)+0.5);//避免浮点误差 
    //sqrt有可能将某个本应是整数的值变成了xxx.9999 可以得到修正
    for(int i=2;i<=m;i++)
    if(n%i==0)
    return 0;

    return 1;
}

(2)

3、

评论

暂无评论