数学归纳法(非常有用的证明方法)
数学归纳原理(弱归纳)
一个包含整数 (1) 的正整数集合如果具有以下性质，即若其包含整数 (k) ,则其也包含整数 (k+1),那么这个集合一定是所有正整数的集合。
高考要考的。
举个栗子,证明:
-
将 (n=1) 代入得 (sum_{i=1}^{1} i^{2} = 1),结论显然成立。
-
假设公式对于 (n) 成立，即 (sum_{i=1}^{n} i^{2}=frac{n(n+1)(2n+1)}{6}) 成立,根据归纳假设有:
则结论成立。
第二数学归纳原理(强归纳)
对于包含 (1) 的正整数集合，如果它具有下述性质:
对于每一个正整数 (n) ,如果它包含全体正整数 (1,2,···,n) ,则它也包含正整数 (n+1) 。
那么这个集合一定是由所有正整数的集合。
斐波那契数
定义: ( f_{1}=1, f_{2}=1, 且对nge 3,有: f_{n}=f_{n-1}+f_{n-2})。
结论1: (sum_{i=1}^{n}f_{i} = f_{n+2}-1)
证明如下:
根据定义可知:
把等式右边展开很容易消掉。
就可以得到结论。
当然，也可以通过数学归纳法进行证明，这里不再赘述。
结论2: 斐波那契数列比公比为 (alpha =frac{1+sqrt[]{5}}{2}) 的等比数列增长得快。
可用第二数学归纳法，证明 (nge 3时，有 f_{n}>alpha^{n-2}):
- 通过计算可得，该不等式对于 (n=3,4) 时成立。
- 假设对于 (kle n) 的所有整数 (k) 该不等式成立。因为 (alpha^2=alpha+1)
则有 :
根据假设，可知
故:
证毕.
结论3:设 (n) 为正整数 (alpha=frac{1+sqrt[]{5}}{2} eta=frac{1-sqrt[]{5}}{2}),则有:
我不会证。
还有亿些性质请读者自行探索。
整除
定义: 如果 (a) , (b) 为整数且 (a e 0) ,我们说 (a) 整除 (b) 是指存在整数 (c) 使得 (b=ac.) 如果 (a) 整除 (b) ，我们还称 (a) 是 (b) 的一个因子，且称 (b) 是 (a) 的倍数.
如果 (a)整除 (b),记为 (amid b) ,如果 (a)不能整除 (b),记为 (a mid b)
废话
整除的简单性质:
- 如果 (a,b,c) 为整数,且 (amid b,bmid c) ,则有 (amid c).
- 如果 (a,b,c,n,m) 为整数且 (cmid a,cmid b),则有 (cmid (na+mb))
给你 (n) 个数 (a_{1},a_{2}···a_{n})，询问对于每一个 (a_{i}) 在数列中有多少数能被 (a_{i})整除。
题解: 本题值域很小，可以根据元素的值建立映射关系，同时统计值域中对于每一个整数的答案，最后输出答案即可。
#include<bits/stdc++.h>
#define N 1000005
using namespace std;
int n,a[N],mp[N],ans[N];
inline int qr()
{
char a=0;int w=1,x=0;
while(a<'0'||a>'9'){if(a=='-')w=-1;a=getchar();}
while(a<='9'&&a>='0'){x=(x<<3)+(x<<1)+(a^48);a=getchar();}
return x*w;
}
int main()
{
n=qr();
int maxn=0;
for(register int i=1;i<=n;i++)
{
mp[a[i]=qr()]++;
maxn=max(maxn,a[i]);
}
for(register int i=1;i<=maxn;i++)
{
if(mp[i])
ans[i]+=mp[i]-1;
for(register int j=i*2;j<=maxn;j+=i)
ans[j]+=mp[i];
}
for(register int i=1;i<=n;i++)
printf("%d
",ans[a[i]]);
return 0;
}
整除分块
求 (sum_{i=1}^{n}k mod i).
题解:
显然, (k mod i=k-lfloor frac{k}{i}
floor)
要求的柿子转化为 (sum_{i=1}^{n}(k-lfloor frac{k}{i} floor)=nk-sum_{i=1}^{n}lfloor frac{k}{i} floor)
而 (lfloor frac{k}{i} floor) 的不同取值数量小于 (2 sqrt[]{n}) 种,理由如下:
将 ([ 1 , n ]) 分为两部分 ([ 1 , sqrt[]{n} ]) 和 (( sqrt[]{n} , n ]).
- 对于 (iin [ 1 , sqrt[]{n} ]) , (lfloor frac{k}{i} floor) 最多有 ( sqrt[]{n}) 种取值。
- 对于 (iin ( sqrt[]{n} , n ]) , (lfloor frac{k}{i} floor) 值域为 ([ 1 , sqrt[]{n} )) , 故最多有 ( sqrt[]{n}-1) 种取值。
综上: (lfloor frac{k}{i} floor) 的不同取值数量小于 (2 sqrt[]{n}) 种.
接下来要求出块的左右端点:
结论: 当有 (lfloor frac{k}{l}
floor=lfloor frac{k}{r}
floor) 时, (r) 的最大取值为(lfloor frac{k}{ lfloor frac{k}{l}
floor}
floor) ,自己证。
之后就可以通过 (l,r) 不断迭代的方式通过本题。
#include<bits/stdc++.h>
#define LL long long
using namespace std;
LL n,k,ans;
inline int qr()
{
int w=1,x=0;char a=0;
while(a<'0'||a>'9'){if(a=='-')w=-1;a=getchar();}
while(a<='9'&&a>='0'){x=(x<<3)+(x<<1)+(a^48);a=getchar();}
return x*w;
}
int main()
{
n=qr();
k=qr();
ans=n*k;
LL l=1,r=0;
while(l<=n)
{
r= k/l!=0?min((k/(k/l)),n):n;
ans-=(r+l)*(k/l)*(r-l+1)/2;
l=r+1;
}
printf("%lld
",ans);
return 0;
}