wxyww

未归档

精品(28) 题解(65)

/ 注册

全部文章 / 未归档（共302篇）

[noip][2017]

Day1T1 30分思路：倒着枚举答案z，用扩展欧几里得求解，如果能找到两个非负整数x,y使得ax+by=z则继续枚举，直到无解为止 100分：最适用与考场上的做法，根据30分思路打表找规律。 30分代码: #include<cstdio> #include<ios...

noip

2018-08-29

0 556

[noip][2017]

Day1T1 30分思路：倒着枚举答案z，用扩展欧几里得求解，如果能找到两个非负整数x,y使得ax+by=z则继续枚举，直到无解为止 100分：最适用与考场上的做法，根据30分思路打表找规律。 30分代码: #include<cstdio> #include<ios...

noip

2018-08-29

0 393

[luogu2822][组合数问题]

题目链接题解: 对于上面和下面的式子进行分解质因数，然后看看上面的质因数个数减去下面的质因数个数能不能达到k的质因数的要求即可。分解质因数的时候用对于阶乘分解质因数的常用方法:比如要求1999！中能分解出多少个5，那么就把1999不断的除以5，并且把得到的数相加即可。原因显然。但是上面...

数论

2018-08-25

0 512

[luogu2822][组合数问题]

题目链接题解: 对于上面和下面的式子进行分解质因数，然后看看上面的质因数个数减去下面的质因数个数能不能达到k的质因数的要求即可。分解质因数的时候用对于阶乘分解质因数的常用方法:比如要求1999！中能分解出多少个5，那么就把1999不断的除以5，并且把得到的数相加即可。原因显然。但是上面...

数论

2018-08-25

0 475

关于gcd的四道题

T1:bzoj2705 题目描述：给定一个n求\(\sum\limits_{i=1}^ngcd(i,n)\) 因为n太大，所以O(n)的做法肯定不行，然后就去想根号的方法。 \[\sum\limits_{i=1}^{n}gcd(i,n)\]\[=\sum\limits_{k|n}k*\su...

数论

2018-08-25

0 393

关于gcd的四道题

T1:bzoj2705 题目描述：给定一个n求\(\sum\limits_{i=1}^ngcd(i,n)\) 因为n太大，所以O(n)的做法肯定不行，然后就去想根号的方法。 \[\sum\limits_{i=1}^{n}gcd(i,n)\]\[=\sum\limits_{k|n}k*\su...

数论

2018-08-25

0 448

[luogu1967][货车运输]

题目链接题意：其实题目的意思就是问从x到y权值最小的路的权值最大能是多少。思路：首先可以先把这张图变成一棵树。因为那些更小的点肯定是不跑更优秀，而且题目没有要求路程，所以生成一棵树，只要能保证在同一个图里面的点能够连通即可。又因为他要使最小权值最大，所以可以只留下那些权值更大的边。所...

最近公共祖先最小生成树

2018-08-21

0 467

[luogu1967][货车运输]

题目链接题意：其实题目的意思就是问从x到y权值最小的路的权值最大能是多少。思路：首先可以先把这张图变成一棵树。因为那些更小的点肯定是不跑更优秀，而且题目没有要求路程，所以生成一棵树，只要能保证在同一个图里面的点能够连通即可。又因为他要使最小权值最大，所以可以只留下那些权值更大的边。所...

最近公共祖先最小生成树

2018-08-21

0 378

数论基础

基础数论快速幂：用来快速求m的n次幂，并取模矩阵乘法：当且仅当前一个矩阵的列数等于第二个矩阵的行数时，可以进行矩阵乘法，矩阵乘法不满***换律，满足结合律.\[C_{ij}=\sum\limits_{k=1}^n{A_{ik}*B_{kj}}\] 方阵可以进行矩阵快速幂。单位矩阵的...

数论

2018-08-20

0 486

数论基础

基础数论快速幂：用来快速求m的n次幂，并取模矩阵乘法：当且仅当前一个矩阵的列数等于第二个矩阵的行数时，可以进行矩阵乘法，矩阵乘法不满***换律，满足结合律.\[C_{ij}=\sum\limits_{k=1}^n{A_{ik}*B_{kj}}\] 方阵可以进行矩阵快速幂。单位矩阵的...

数论

2018-08-20

0 404