小知识（二分幂）

把以前大神们讲过的一些小知识点整理了一下。

1.二分幂的原理：

代码：

 1 int power(int a,int b)
 2 {
 3     int ans=1;
 4     while(b!=0)
 5     {
 6         if(b%2==1)
 7             ans*=a;
 8         b/=2;
 9         a*=a;
10     }
11     return ans;
12 }

 1 double power(double b,unsigned int e)
 2 {
 3     if(e==0)
 4         return 1;
 5     if(e==1)
 6         return b;
 7     double result=power(b,e/2);
 8     result*=result;
 9     if(e%2)//a&0x1=a%2;
10         result*=b;
11     return result;
12 }

由二分幂来求出a的b次方的最后一位数：HDU1079

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<queue>
 6 #include<vector>
 7 using namespace std;
 8 long long power(long long a,long long b)
 9 {
10     long long  ans=1;
11     long long temp=a;
12     while(b!=0)
13     {
14         if(b%2==1)
15             ans=(ans*temp)%10;
16         b/=2;
17         temp=(temp%10)*(temp%10)%10;;
18     }
19     return ans;
20 }
21 int main()
22 {
23     long long  a,b;
24     long long s;
25     while(cin>>a>>b)
26     {
27         s=power(a,b);
28         cout<<s<<endl;
29     }
30     return 0;
31 }

View Code

2.素数筛选法：

图片更直观：删去2,3,5,7....的倍数，直到数组中所有的数都是素数。

代码：

 1 const int maxn=1000005;
 2 bool is[maxn];
 3 int prime[maxn];
 4 int main()
 5 {
 6     int i,j;
 7     memset(is,false,sizeof(is));    
 8     is[1]=true;
 9     int cnt = 0;
10     for(i=2;i*i<maxn;i++)
11     {
12         if(!is[i])
13         {
14             for(j=i*i;j<maxn;j+=i)//i的倍数
15                 is[j]=true;
16         }
17     }
18     for(i=2;i<maxn;i++)
19     {
20         if(!is[i])
21             prime[cnt++]=i;//cnt素数的个数
22     }

3.求最大公约数（gcd）:

1 int gcd(int a,int b)
2 {
3 if(b==0)  return a;
4 else return gcd(b,a%b);
5 }

最小公倍数：lcm(a,b)=a*b/(gcd(a,b));

4.快速幂：用于求解a的b次方，b的值很大。

求x^n次方，n=2^k1+2^k2+2^k3+..., x^n=x^2^k1*x^2^k2*x^2^k3*..., 如x^20=x^16*x^4;

 1 typedef long long LL;
 2 LL fun(LL x,LL n,)
 3 {
 4     LL res=1;
 5     while(n>0)
 6     {
 7         if(n & 1)
 8             res=(res*x)%mod;
 9         x=(x*x)%mod;
10         n >>= 1;//右移位
11     }
12     return res;
13 }