小模板

欧几里得求公约数：

 1 int gcd(int a, int b)
 2 {
 3     while (b)
 4     {
 5         int tmp = b;
 6         b = a % b;
 7         a = tmp;
 8     }
 9     return a;
10 }

View Code

筛选法求素数：

 1 int prime()
 2 {
 3     memset(vis, true, sizeof(vis));
 4     for(int i = 2; i <= sqrt(N +0.5); i++)
 5         if(vis[i])
 6             for(int j = i << 1 ; j <= N; j += i)
 7                 vis[j] = false;
 8     int k=0;
 9     for(int i = 2 ; i <= N; i++)
10         if(vis[i])
11             pri[k++]=i;
12 }

View Code

杨辉三角求组合数：
方法1：

1 memset(c,0,sizeof(c));
2 c[0]=1;
3 repu(i,1,sum+1)
4 c[i]=c[i-1]*(sum-i+1)/i;

View Code

方法2：

1 memset(c,0,sizeof(c));
2 for(int i=1;i<=n;i++)
3 {
4     c[i][0]=1;
5     for(int j=1;j<i;j++)
6         c[i][j]=c[i-1][j-1]+c[i-1][j];
7 }

View Code

求欧拉数

 1 mem(phi,0);
 2     phi[1]=1;
 3     for(int i=2; i<=N; i++)
 4     {
 5         if(!phi[i])
 6         {
 7             for(int j=i; j<=N; j+=i)
 8             {
 9                 if(!phi[j])
10                     phi[j]=j;
11                 phi[j]=phi[j]/i*(i-1);
12 } } }
13 快速幂取模
14 
15 ll pow_mod(ll x, ll y)
16 {
17     ll ans = 1;
18     while (y > 0)
19     {
20         if (y & 1)
21             ans = ans * x % mod;
22         y >>= 1;
23         x = x * x % mod;
24     }
25     return ans;
26 }

View Code

统计数字模板：

 1 void count_digits(int s,int ans[],int times=1)
 2 {
 3     int i,d,p;
 4     if (s <= 0)
 5         return ;
 6     d = s % 10;
 7     p = s / 10;
 8     for (i = 1; i <= d; i ++)
 9         ans[i] += times;
10     while(p > 0)
11     {
12         ans[p % 10] += (d + 1) * times;
13         p = p / 10;
14     }
15     for (i = 0; i <= 9; i ++)
16         ans[i] += times * (s / 10);
17     times *= 10;
18     count_digits((s / 10)-1,ans,times);
19     return ;
20 }

View Code

分解质因子：

 1 void tran(int n,int a[])
 2 {
 3     repu(j,2,n+1)
 4     {
 5         int k=j;
 6         for(int i=0; i<1229; i++)
 7         {
 8             while(k%pri[i]==0)
 9             {
10                 k/=pri[i];
11                 a[i]++;
12             }
13             if(k==1)
14                 break;
15         }
16     }
17 }

View Code

快速幂取余

 1 long long  Pow(long long  a,long long  b,long long  n)
 2 {
 3     long long  t,y;
 4     t = 1;
 5     y = a;
 6     while(b)
 7     {
 8         if(b % 2) t = t * y % n;
 9         y = y * y % n;
10         b >>= 1;
11     }
12     return t;
13 }

View Code

快速乘法

 1 ///每2个x相加取余，然后m/=2
 2 ll quickmul(ll x,ll m)
 3 {
 4     ll re=0;
 5     while(m)
 6     {
 7         if(m%2)
 8         {
 9             re=(re+x)%p;
10         }
11         x=(x+x)%p;
12         m>>=1;///m/=2;
13     }
14     return re;
15 }

View Code