#创作计划#编程里你绝对用得到的数学公式

C++真真真难啊啊啊

2025-08-30 09:57:52

发布于：上海

4阅读

0回复

0点赞

first of all辗转相除法
1.第一条：什么是辗转相除法（the definition of "辗转相除法") $\color{silver}{咋么能show出我贼烂的english呢}$

我们先解刨分解一下辗转相除法这几个字

顾名思义：辗转表示重复进行相当于while;而相除就表示互相除以

所以辗转相除法就进化为，啊，不，退化成“重复进行互相除以法” $\color{red}{\boxed{难怪要说成辗转相除法，翻译出来这么长}}$

2. 第二条：辗转相除法咋么用 $\color{orange}{不写English了}$
所谓 相除，就是要有两个数 就让两个数定义为（a和b)吧
首先让a / b得到商d和余数r
接着我们用b / d继续得到商d2和余数r2
就这样 我们重复用现有的除数除以商
直到余数为零时停止
就这样辗转相除法就结束了
我们发现辗转相除法就是求出(a,b)的最大公因数的
不知道各位读者有没有理解辗转相除法咋么用呢？

没理解?~~猪都能理解，你不能理解~~ $\color{skyblue}{\boxed{开个玩笑}}$

没事，请看VCR $\color{fuchsia}{\boxed{好老的梗}}$

现在你学废了吗 $\color{green}{再没学会，你就废了}$

3.第三条代码部分
//递归实现程序
int Gcd(int a, int b){
   if(a % b == 0){
       return b;
   }
   return Gcd(b, a % b);
}

好了 ACGO_OK 第一个数学公式我们顺利地讲好了
接下来我们转向chapter2

埃氏筛法
当你要在1~N之间找出所有的素数时......
你就会发现会TLE。这时就需要埃氏筛。
埃氏筛原理：要得到自然数n以内的全部素数，必须把不大于根号n 的所有素数的倍数剔除，剩下的就是素数。
方法：给出要筛数值的范围n，找出以内的素数。先用2去筛，即把2留下，把2的倍数剔除掉；再用下一个质数，也>>就是3筛，把3留下，把3的倍数剔除掉；接下去用下一个质数5筛，把5留下，把5的倍数剔除掉；不断重复下去......
具体样例代码：
#include <bits/stdc++.h>
using namespace std;
int n;
int main() {
   cin>>n;
   int a[n+1]={0};
   a[1]=1;
   for(int i=1;i<=n;i++){
       if(a[i]==0){
          for(int j=2*i;j<=n;j+=i){
             a[j]=1;
          }
       }
   }
   int cnt=0;
   for(int i=2;i<=n;i++){
       if(a[i]==0)cnt++;
   }
   cout<<cnt;
   return 0;
}
当然强中自有强中手

线性筛

登场！！！！

但是主播手打累了，所以请线性筛先下台，过两年半再找你