1. 欧拉质数筛
功能是给一个整数n查找小于等于n的所有质数。
最后使用的是prime【i】
//功能：查找n内第x个质数。
bool isprime[100000010]; //isprime[i]=1表示:i是素数
int prime[6000010],cnt=0;//prime存质数
void getprime(int n){ //筛到n 也就是n以内的质数
memset(isprime, 1, sizeof isprime);
isprime[1] = 0;
for(int i=2;i<=n;i++){
if(isprime[i]){ //没筛掉
prime[++cnt] = i;
}
for(int j = 1; j<=cnt&&i*prime[j]<=n;j++){
//从Prime[1]，即最小质数2开始，逐个枚举已知的质数，并期望Prime[j]是(i*Prime[j])的最小质因数
//当然，i肯定比Prime[j]大，因为Prime[j]是在i之前得出的
isprime[i*prime[j]] = 0;
if(i % prime[j] == 0)//i中也含有Prime[j]这个因子 确定prime[j]是prime[j]*i的最小质因数
break; //重要步骤。见原理
}
}
}
2. 区间质数筛
亿级 的数量级，遍历肯定会超时，所以我们使用美猴王合数的一个性质:可以分解为两个不为1且不等于本身的因子相乘 即 n=a*b(n为合数)
所以在1~500000中我们是可以找到500000^2的数的质因子的。所以我们可以晒出所有的合数，剩下的就是质数啦。
- 筛出1-50000中的所有质数,并且对合数打上标记.
- 在L-R的范围呢用我们已求出的质数筛出其中的合数(设p为质数,则i*p一定不为质数),并对其打上标记
- 遍历L-R,没有打标记的元素即为我们所求的素数
//线性筛
void gprime(){
for(int i=2;i<=50000;i++){
if(!vis[i]) prime[++cnt] = i;
for(int j=1;i*prime[j]<=50000;j++){
vis[i*prime[j]] = 1;
if(i%prime[j] == 0) break;//目的是保证prime[j]是最小质因数
}
}
}
void solve(){
cin>>l>>r;
if(l==1) l=2;
gprime();//筛出根号r内所有的质数和剩下的合数。
memset(vis,0,sizeof vis);
for(int i=1;i<=cnt;i++){
LL p = prime[i];
LL start = (l+p-1)/p*p>2*p?(l+p-1)/p*p:2*p;//找到大于l的第一个能被p整除的数开始。
for(LL j = start;j<=r;j+=p)
vis[j-l+1]=1; //从j开始标记，会爆空间，所以我们进行压缩。如果不想这样做也可以使用map，但是不方便。
}
for(int i=1;i<=r-l+1;i++) if(!vis[i]) ans++;//那在这里我们就用区间之差来查找 这里和上面的prime是两个数组，所以不用担心交错。
cout<<ans<<endl;
}
3. 组合数问题
普通组合数C(a,b)转换成杨辉三角的模型
如果是只要求前几个的话直接先乘后除就好了，比如Ci2什么的。
牢记公式：C(i , j) = C(i-1 , j) + C(i-1 , j-1)
预处理的话，就处理C11 = 1 然后Ci0 = 1
另外的，如果我们想知道在i和j在一个合法范围之内0<=i<=n,0<=j<=min(i,m)有多少对i，j满足Cij是k的倍数，我们需要求个数。做法是矩阵求和。
void func(){
//求组合数。
c[1][1] = 1;
for(int i=0;i<=2000;i++){
c[i][0] = 1;
}
for(int i=2;i<=2000;i++){
for(int j=1;j<=i;j++){
c[i][j] = (c[i-1][j] + c[i-1][j-1])%k; //取k模为0说明是倍数。0倍也算
}
}
//矩阵求和求个数 优化n次查询
for(int i=2;i<=2000;i++){
for(int j=1;j<=i;j++){
s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1];
if(c[i][j] == 0) s[i][j] +=1;
}
s[i][i+1]=s[i][i];//继承.
}
}
//另外我们在最后输出结果的时候，如果有m>n也就是Cij的j>i的情况，只要输输出Snn就好了。