数学知识小记
2017/05/19 12:12:53.
真de弱智，今天连等差数列求和公式都忘了...
1.等差数列.
通项公式:a(n) = a(1) + (n-1)*d;
前n项和: S(n) = n*a(1) + n*(n-1)/2*d;
变形:S(n) = (a(1) + a(n))*n/2;
2.等比数列.
通项公式:a(n) = a(1)*q^(n-1);
前n项和:S(n) = a(1)*(1 - q^n)/(1-q);
变形:S(n) = (a(1) - a(n)*q)/(1-q);
2017/06/28 00:46:41
regular convex polygon with n sides.(具有n条边的规则凸多边形)
求内角度和为：(n-2)*180
所以求规则凸多边形的单个内角度为：(n-2)*180/n
2017/07/06 17:46:52
因数：不包括零的任意数(正数和负数)。
正因数：不包括零的任意正数。
2017/07/29 23:45:47
鸽巢原理：
n+1个物体放入n个盒子，那么至少有一个盒子包含两个或更多的物体。
应用：
n个数中，必然存在j,k(j<=k)满足Aj,Aj+1...Ak-1,Ak的和是n的倍数。
分析：进行求(A1),(A1+a2),(A1+A2+A3),...,(A1+A2...An)。
① 如果存在一个%n = 0的，则直接证明得存在。
② %n都不等于0，而%n不为0的个数为n-1个，则根据鸽巢原理能够得到肯定存在两个或更多模数相同的数，所以找到这两个模数相同的位置便是j，k。
2017/07/31 15:06:21
求一个数的所有质因子
#include <stdio.h>
int num[1005], cnt;
void ZhiYinZi(int n)
{
cnt = 0;
for(int i = 2 ; i*i <= n; ++i)
{
if(n%i == 0)
{
num[++cnt] = i;
while(n%i == 0) n /= i;
}
}
if(n > 1) num[++cnt] = n;
}
int main()
{
int n; scanf("%d", &n);
ZhiYinZi(n);
for(int i = 1; i <= cnt; ++i)
printf("%d ", num[i]);
puts("");
return 0;
}
O(1)求从1到N的异或：
LL xor_n(LL n)
{
LL t = n & 3;
if(t & 1) return t/2ll^1;
return t/2ll^n;
}
判断组合数的奇偶性：
int isodd(int n, int m)
{
while(m)
{
if((m&1) && !(n&1)) return 0;
m >>= 1, n >>= 1;
}
return 1;
}
//OR
int isodd(int n, int m)
{
return (n&m) == m;
}
给定两个数m,n，求m!分解质因数后因子n的个数。如果相乘直接求的话会超出数据类型的范围。下面给出一种效率比较高的算法，我们一步一步来。
m! = 1*2*3*……*(m-2)*(m-1)*m
可以表示成所有和n的倍数有关的乘积再乘以其他和n的倍数没有关系的
= (n*2n*3n*......*kn)*other
other是不含n因子的数的乘积，因为 kn<=m 而k肯定是最大值，所以 k = m/n
= n^k*(1*2*......*k)*other
= n^k*k!*other
从这个表达式中可以提取出k个n，然后按照相同的方法循环下去可以求出k!中因子n的个数。
每次求出n的个数的和就是m!中因子n的总个数。
ll work(int m, int b)
{
ll ans = 0;
while(m)
{
m /= b;
ans += m;
}
return ans;
}
静待更新...