北京网站建设首选小峰,logo头像设计,科技网站建设 长沙,苏州行业网站建设服务秋名山码民的主页 #x1f389;欢迎关注#x1f50e;点赞#x1f44d;收藏⭐️留言#x1f4dd; #x1f64f;作者水平有限#xff0c;如发现错误#xff0c;还请私信或者评论区留言#xff01; 目录一、欧几里得二、扩展欧几里得三、算术基本定理四、线性筛选求质数五… 秋名山码民的主页 欢迎关注点赞收藏⭐️留言 作者水平有限如发现错误还请私信或者评论区留言 目录一、欧几里得二、扩展欧几里得三、算术基本定理四、线性筛选求质数五、等差数列六、等比数列七、组合计数最后一、欧几里得
求最大公约数的一种常用方法
public static int gcd(int a, int b) {return b ! 0 ? gcd(b, a % b) : a;
}二、扩展欧几里得
求xy使得axby gcd(a,b) public static int exGcd(int a,int b,int x,int y){if(b 0){x 1;y 0;return a;}int d exGcd(b,a%b,y,x);y - (a/b)*x;return d;}三、算术基本定理
算术基本定理又称为正整数的唯一分解定理即每个大于1的自然数要么本身就是质数要么可以写为2个或以上的质数的积而且这些质因子按大小排列之后写法仅有一种方式。 证明参考维基百科
四、线性筛选求质数
在O(N)的时间复杂度内求出来1 ~ n中所有的质数以及每一个数的最小质因子。 private static void get_primes(int n) {for (int i 2; i n; i) {if (!st[i]) primes[cnt] i;for (int j 0; primes[j] * i n; j) {/*因为prime中素数是递增的所以如果i%prime[j]!0代表i的最小质因数还没有找到即i的最小质因数大于prime[j]也就是说prime[j]就是i*prime[j]的最小质因数于是i*prime[j]被它的最小质因数筛掉了*/st[primes[j] * i] 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 (i % primes[j] 0) break; // 通过最小质因子来筛}}}五、等差数列
这俩个数列学过高中数学的应该都清楚我就不加以证明了。
1246. 等差数列
import java.util.Arrays;
import java.util.Scanner;/*** Author 秋名山码神* Date 2023/2/17* Description*/
public class Main {static int N 100010;static int[] a new int[N];public static int gcd(int a,int b){return b ! 0 ? gcd(b,a%b) : a;//b!0 , 递归计算gcd(b,a%b)}public static void main(String[] args) {Scanner sc new Scanner(System.in);int n sc.nextInt();for(int i 0; in; i)a[i] sc.nextInt();Arrays.sort(a,0,n);int d 0;for(int i 1; in; i)d gcd(d,a[i] - a[0]);if(d 0){System.out.println(n);}else {System.out.println((a[n-1] - a[0]) / d 1);}}
}
六、等比数列
P8636 蓝桥杯 2016 省 AB 最大比例
#includeiostream
#includealgorithmusing namespace std;const int N110;typedef long long LL;LL x[N],a[N],b[N];
int cnt0;//假设原数列为 a,a*(p/q)^1,a*(p/q)^2,...,a*(p/q)^(n-1)
//假设抽取的数列 b0,b1,...,b(N-1) (从小到大排好序了)
// b1/b0,b2/b0,...,b(N-1)/b0-- (p/q)^x1,(p/q)^x2,...,(p/q)^x(N-1)
// 我们要求的是 p/q^k (p/q)1,所以使k最大即求 x1~x(N-1)的最大公约数
//这里我们使用更相减损术因为我们没有得到确切的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总的才华
//把分子分母分别去算结果是相同的因为分子分母的幂次是相同的
LL gcd(LL a,LL b)
{return b? gcd(b,a%b):a;
}LL gcd_sub(LL a,LL b)
{if(ab) swap(a,b); //更相减损术总是大减小它们的底数是一样的if(b1) return a;return gcd_sub(b,a/b);
}int main()
{int n;cinn;for(int i0; in; i) scanf(%lld,x[i]);sort(x,xn);for(int i1; in; i){if(x[i] ! x[i-1]){LL dgcd(x[i],x[0]); a[cnt]x[i] / d; //得到x[i]/x[0]的分子b[cnt]x[0] / d; //得到x[i]/x[0]的分母cnt;}}LL upa[0],downb[0];for(int i1; icnt; i){upgcd_sub(up,a[i]); //两两求最大公约数downgcd_sub(down,b[i]);}coutup/downendl;return 0;
}七、组合计数
加法原理 若完成一件事的方法有n类其中第i类方法包括ai种不同的方法且这些方法互不重合则完成这件事共有a1a2…an种不同的方法。 乘法原理 若完成一件事需要n个步骤其中第i个步骤有ai种不同的完成方法且这些步骤互不干扰则完成这件事共有a1a2…*an种不同的方法
排列数 从n个不同的元素中依次取出m个元素排成一列产生的不同排列的数量为 组合数 从n个元素中取出m个元素组成一个集合不考虑顺序产生的不同集合的数量为 计算系数
//杨辉三角做法
#includeiostream
using namespace std;
long long x[1010][1010];
int main()
{long long a,b,k,n,m;cinabknm;x[1][1]1;for(int i2;ik1;i) for(int j1;ji;j)x[i][j](x[i-1][j-1]*bx[i-1][j]*a)%10007;coutx[k1][m1];return 0;
}二项式做法
最后
数论的知识太多了这是我最近三天想到的后续有时间再补充吧
