得二、扩展欧几里得三、算术基本定理四、线性筛选求质数五、等差数列六、等比数列七、组合计数最后一、欧几里得

public

算术基本定理又称为正整数的唯一分解定理即每个大于1的自然数要么本身就是质数要么可以写为2个或以上的质数的积而且这些质因子按大小排列之后写法仅有一种方式。

证明参考维基百科

{/*因为prime中素数是递增的所以如果i%prime[j]!0代表i的最小质因数还没有找到即i的最小质因数大于prime[j]也就是说prime[j]就是i*prime[j]的最小质因数于是i*prime[j]被它的最小质因数筛掉了*/st[primes[j]

true;

把质数的i倍筛掉/*如果当i%prime[j]0时代表i的最小质因数是prime[j]那么i*prime[jk](k0)这个合数的最小质因数就不是prime[jk]而是prime[j]了所以i*prime[jk]应该被prime[j]筛掉而不是后续的prime[jk]于是在此时break*/if

primes[j]

sc.nextInt();Arrays.sort(a,0,n);int

0;for(int

a,a*(p/q)^1,a*(p/q)^2,...,a*(p/q)^(n-1)

b0,b1,...,b(N-1)

(p/q)^x1,(p/q)^x2,...,(p/q)^x(N-1)

p/q^k

//这里我们使用更相减损术因为我们没有得到确切的x1~x(N-1)是多少我们只有(p/q)^x1,(p/q)^x2,...,(p/q)^x(N-1)这些的值/*更相减损术第一步任意给定两个正整数判断它们是否都是偶数。

若是则用2约简若不是则执行第二步。

第二步以较大的数减较小的数接着把所得的差与较小的数比较并以大数减小数。

继续这个操作直到所得的减数和差相等为止。

则第一步中约掉的若干个2的积与第二步中等数的乘积就是所求的最大公约数。

*///更相减损术总用较大的减去较小的

/*例子98-633563-352835-28728-72121-71414-77

所以98和63的最大公约数等于7。

*///我们这里要用更相减损术的是指数所以要让(p/q)^x1,(p/q)^x2,...,(p/q)^x(N-1)两两计算互除除到结果为1,即x1x2,此时幂次为0结果为1这其实就是y总的思路再次感叹y总的才华

gcd(LL

scanf(%lld,x[i]);sort(x,xn);for(int

i1;

//两两求最大公约数downgcd_sub(down,b[i]);}coutup/downendl;return

}七、组合计数

若完成一件事的方法有n类其中第i类方法包括ai种不同的方法且这些方法互不重合则完成这件事共有a1a2…an种不同的方法。

乘法原理

若完成一件事需要n个步骤其中第i个步骤有ai种不同的完成方法且这些步骤互不干扰则完成这件事共有a1a2…*an种不同的方法

排列数

从n个不同的元素中依次取出m个元素排成一列产生的不同排列的数量为

组合数

从n个元素中取出m个元素组成一个集合不考虑顺序产生的不同集合的数量为

计算系数

a,b,k,n,m;cinabknm;x[1][1]1;for(int

i2;ik1;i)

j1;ji;j)x[i][j](x[i-1][j-1]*bx[i-1][j]*a)%10007;coutx[k1][m1];return

}二项式做法