首页 > 代码库 > 数论大整理(不定时更新)(虽然是懵着听下来的)x
数论大整理(不定时更新)(虽然是懵着听下来的)x
一、斐波那契数列：
1 #include<iostream> 2 #include<cmath> 3 using namespace std; 4 int main() 5 { 6 double a,n,ans; 7 cin>>n; 8 //n--; //(第一项是0时) 9 a=sqrt(5);10 ans =(a/5) * (pow( (1+a)/2 ,n) - pow((1-a)/2 ,n));11 cout<<ans; 12 return 0; 13 }
1 #include<iostream> 2 #include<cmath> 3 #include<cstdio> 4 using namespace std; 5 int a[10001]; 6 int main() 7 { 8 int n; 9 a[1]=1;10 a[2]=1;11 scanf("%d",&n);12 for(int i=3;i<=n;i++)13 {14 a[i]=a[i-1]+a[i-2];15 }16 cout<<a[n];17 return 0;18 }
1 #include<iostream> 2 #include<cmath> 3 #include<cstdio> 4 using namespace std; 5 int a[10001]; 6 int f(int n) 7 { 8 if(n==1||n==2)return 1; 9 else return f(n-1)+f(n-2);10 }11 int main()12 {13 int n;14 a[1]=1;15 a[2]=1;16 scanf("%d",&n);17 printf("%d",f(n));18 return 0;19 }
二、素数：
详细请见http://www.cnblogs.com/zxqxwnngztxx/p/6735297.html
在这里仅仅给出线性筛法求素数的代码：
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 6 using namespace std; 7 8 const int MAXN=10001; 9 10 int vis[MAXN];11 12 int main()13 {14 int n;15 scanf("%d",&n);16 for(int i=2;i<=sqrt(n);i++)17 {18 if(vis[i]==0)19 {20 for(int j=i*i;j<=n;j=j+i)21 {22 vis[j]=1;23 }24 }25 }26 for(int i=2;i<=n;i++)27 {28 if(vis[i]==0)29 printf("%d ",i);30 }31 return 0;32 }
三、（扩展）欧几里得算法(裴蜀定理)：
详细请见：http://www.cnblogs.com/zxqxwnngztxx/p/6741002.html
codevs有道题（同余方程）可以去做做试试：http://codevs.cn/problem/1200/
1 #include<iostream> 2 using namespace std; 3 int main() 4 { 5 int n,m,r; 6 cin>>m>>n; 7 r=m%n; 8 while(r!=0) 9 {10 m=n;11 n=r;12 r=m%n;13 }14 cout<<n;15 }
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 5 using namespace std; 6 7 long long exgcd(long long a,long long b,long long &x,long long &y) 8 { 9 if(b==0)10 {11 x=1;12 y=0;13 return a;14 }15 long long r=exgcd(b,a%b,x,y),t=x;16 x=y;y=t-y*(a/b);17 return r; 18 }19 20 int main()21 {22 long long a1,b1,x1,y1;23 cin>>a1>>b1;24 exgcd(a1,b1,x1,y1);25 while(x1<0) x1+=b1;26 cout<<x1;27 return 0;28 }
数论大整理(不定时更新)(虽然是懵着听下来的)x
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。