！！！参考《ACM国际大学生程序设计竞赛算法与实现》

求n!中含有某个因子个数的方法

转载自https://www.cnblogs.com/dolphin0520/archive/2011/04/11/2012891.html

1
2
3
4
5
6
7
8
9
10
int count(int n,int k)
{
    int num=0;
    while(n)
    {
        num+=n/k;
        n/=k;
    }
    return num;
}
求一个阶乘中含有的素因子2的个数

n!共

n+n2+n22+⋅⋅⋅+n2k（整除）n+ \frac{n}{2}+\frac{n}{2^2}+···+\frac{n}{2^k}（整除）

个二

即把它分解成二进制位,如（10100）2（10100）_2 ，因数2的个数为 （1010）2+（101）2+（10）2+（1）2（1010）_2+（101）_2+（10）_2+（1）_2_
我的观点是(10100)2=(10000)2+(100)2(10100)_2 =(10000)_2 +(100)_2

而$(10000)_2 的贡献为 (10000)_2 - 1,(100)_2 的贡献为 $$(100)_2 - 1$

所以n!中因子2的个数为 n -（n的二进制中一的个数）

组合数奇偶性的判断

转载自https://blog.csdn.net/kongming_acm/article/details/5965243

回归此题

  • 最直观的方法就是计算一下，然后看它的奇偶性；

  • 对于给定C(n,m)，检查n中2因子的个数与m和(n-m)中2因子个数和的关系，假设n!中2因子个数为a，m!中2因子个数为b，(n-m)!中2因子个数为c，则显然有a>=(b+c)；并且当a==b+c时，一定为奇，否则为偶。

    题意转化为求a和b+c。求一个阶乘中含有的素因子i的个数的方法，但是有的时候，这种方法仍然太慢（比如TOJ的一道题目，要判断5000000次），更快的方法是什么呢？ 方法三：由方法2可以很容易地看出，n!中含有2因子的个数等于(n-它的二进制形式中1的个数)（每除一次如果有1的话去掉一个1）。那么题意再次转化为求m,n-m以及n的二进制形式中1的个数。或者说，看n&m ?= m，这个呢，如果等于，那么也就意味着，所有m中为1的位置n一定为1，那么n-m就可以直接用二进制减，这样得到的差的二进制中1的个数加上m中二进制1的位数正好等于n中1的位数，由前面可以知道，这就是一个奇数

gcd&ex_gcd

1
2
3
4
5
6
7
8
9
10
11
12
13
int gcd(int a,int b){
     return a==0?b:gcd(b%a,a);
}
int ex_gcd(int a,int b,int &x,int &y){
    if(b==0){
        x=1;y=0;return a;
    }
    else{
        int r=ex_gcd(b,a%b,y,x);
        y-=x*(a/b);
        return r;
    }
}
贝祖定理

a,b是整数，则存在整数x,y，使得ax+by=gcd（a,b）。

算法:欧几里得算法

由贝祖定理得,gcd(a,b)=gcd(b,a-b) 其中a≥b。不断迭代，直到b=0，此时a为原数对的最大公因数。

同理 gcd(a,b)=gcd(b,a mod b) 。可在log时间内求得两数gcd。

算法：拓展欧几里得算法

若 gcd(a,b) = d，求 m,n 使得 d = ma + nb .

利用每次的商，来倒推一组解。

当b=0时，有m=1，n=0 成立。

当b>0时，由欧几里得算法 gcd(a,b)=gcd(b,a mod b) ,

先递归求出一组解 x，y 。

b · x + （a mod b ) · y = gcd(b,a mod b) = gcd(a,b)

b · x + (a - a div b · b) · y = gcd（a,b )

a · y + b · （x - a div b · y) = gcd(a,b)

故 n=y，m=x - a div b · y

逆元（inv）

1
2
3
4
5
6
int inv(int a,int m){
    int x,y,t;
    t=ex_gcd(a,m,x,y);
    if(t!=1) return -1;
    else return x;
}

当计算：$$a\times x \equiv b(mod\ m)$$，我们希望把 a 除到右边。但不能直接除,然而乘法可以。记a的逆元为$$a^{-1}$$

a⋅a−1≡1(mod m)a · a^{-1} \equiv 1(mod\ m)

求逆元要求gcd(a,m)=1

∵\becausegcd(a,m) = 1 ∴\therefore ∃s,t\exists s,t s·a + t·m = 1

$ \therefore s·a + t·m \equiv {1} (mod \ m) , t · m \equiv 0 (mod \ m) \ , s · a \equiv 1 (mod\ m) $

所以可以通过ex_gcd 来求逆元

a−1=sa^{-1} = s

类欧几里得算法

转载自https://www.cnblogs.com/LLppdd/p/8428349.html
问题：
$ f(a,b,c,n)=\sum_{i=0}^n\lfloor\frac{ai+b}{c}\rfloor $

f(a,b,c,n)=∑i=0n⌊aci+bc⌋f(a,b,c,n)=\sum_{i=0}^n\lfloor\frac{a}{c}i+\frac{b}{c}\rfloor

其实这个函数的几何意义是一次函数 y=aci+bcy=\frac{a}{c}i+\frac{b}{c} 下 x∈[0,n] 整点的个数（包含直线上的点，但是不包含 y=0的点） （这个可以从上面的式子看出的哦）

设m=⌊an+bc⌋m=\lfloor\frac{an+b}{c}\rfloor

f(a,b,c,n)=∑i=0n ∑j=1m [ai+bc>=j]f(a,b,c,n)=\sum_{i=0}^n\ \sum_{j=1}^m\ [\frac{ai+b}{c}>=j]

f(a,b,c,n)=∑i=0n ∑j=0m−1 [ai+bc>=j+1]f(a,b,c,n)=\sum_{i=0}^n\ \sum_{j=0}^{m-1}\ [\frac{ai+b}{c}>=j+1]

f(a,b,c,n)=∑i=0n ∑j=0m−1 [ai>=cj+c−b]f(a,b,c,n)=\sum_{i=0}^n\ \sum_{j=0}^{m-1}\ [ai>=cj+c-b]

f(a,b,c,n)=∑i=0n ∑j=0m−1 [ai>cj+c−b−1]f(a,b,c,n)=\sum_{i=0}^n\ \sum_{j=0}^{m-1}\ [ai>cj+c-b-1]

f(a,b,c,n)=∑i=0n ∑j=0m−1 [i>(caj+c−b−1a)]f(a,b,c,n)=\sum_{i=0}^n\ \sum_{j=0}^{m-1}\ [i>(\frac caj+\frac{c-b-1}a)]

f(a,b,c,n)=∑j=0m−1 [n−(caj+c−b−1a)]f(a,b,c,n)=\sum_{j=0}^{m-1}\ [n-(\frac caj+\frac{c-b-1}a)]

f(a,b,c,n)=nm−∑j=0m−1 [caj+c−b−1a]f(a,b,c,n)=nm-\sum_{j=0}^{m-1}\ [\frac caj+\frac{c-b-1}a]

f(a,b,c,n)=nm−f(c,c−b−1,a,m−1)f(a,b,c,n)=nm-f(c,c-b-1,a,m-1)

f(1,2,3,4)
p1.png

https://www.cnblogs.com/LLppdd/p/8428349.html

http://www.fooplot.com

欧拉函数

定义：ϕ(n)\phi(n)为小于等于n的数中与n互质的数的个数

  • ϕ(1)\phi(1)=1

  • 若$ n=p^k ,p为质数则, p为质数则\phi(n)=pk-p{k-1}=(p-1)p^{k-1} $

    //为什么：如353^5可以发现{3∗k,∣1<=k<=3k−1}\{3*k,|1<= k <= 3^{k-1} \} 都不和它互质。

  • 若m，n互质，ϕ(mn)=ϕ(m)×ϕ(n)\phi(mn)=\phi(m)\times\phi(n)

单变元模线性方程组