[ACM实例代码] 01背包 完全背包 快速幂 筛法求素数

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<math.h>
 4 
 5 const int max_n=2300;
 6 const int max_m=5000;
 7 const int primen=1000000;
 8 
 9 bool prime[primen];
10 
11 
12 typedef long long LL;
13 
14 int max(int a,int b)
15 {
16     return a>b?a:b;
17 }
18 
19 void package_all(void)                  //完全背包
20 {
21     int w[max_n]={7,4,10,2,9,8};
22     int v[max_n]={9,9,20,5,7,6};
23     int dp[max_m];
24     int N,V;
25     N=6;
26     V=200;
27     memset(dp,0,sizeof(dp));
28     for(int i=0;i<N;i++)
29         for(int vi=v[i];vi<=V;vi++)
30             dp[vi]=max(dp[vi],dp[vi-v[i]]+w[i]);
31     for(int i=0;i<=V;i++) printf("%d\n",dp[i]);
32 }
33 
34 void package01(void)                    //01背包
35 {
36     int w[max_n]={7,4,10,2,9,8};
37     int v[max_n]={9,9,20,5,7,6};
38     int dp[max_m];
39     int N,V;
40     N=6;
41     V=200;
42     memset(dp,0,sizeof(dp));
43     for(int i=0;i<N;i++)
44         for(int vi=V;vi>=v[i];vi--)
45             dp[vi]=max(dp[vi],dp[vi-v[i]]+w[i]);
46     for(int i=0;i<=V;i++) printf("%d\n",dp[i]);
47 }
48 
49 LL quick_pow(LL a,LL b,LL c) //a^b mod c    快速幂
50 {
51     LL res=1;
52     printf("%lld^%lld mod %lld is ",a,b,c);
53     while(b)
54     {
55         if(b&1)
56         {
57             res=res*a%c;
58         }
59         a=a*a%c;
60         b>>=1;
61     }
62     printf("%lld\n",res);
63     return res;
64 }
65 
66 void make_prime(void)                   //经典筛法求素数
67 {
68     prime[0]=prime[1]=0;
69     prime[2]=1;
70     for(int i=3;i<=primen;i++)
71         prime[i]=i%2;
72     for(int i=3;i<=(int)sqrt(primen*1.0);i++)
73     {
74         if(prime[i])
75         {
76             for(int j=i+i;j<=primen;j+=i)
77                 prime[j]=0;
78         }
79     }
80     for(int i=0;i<=1000;i++)
81         if(prime[i]) printf("%d ",i);
82 }
83 
84 int main(void)
85 {
86     make_prime();
87     printf("\n");
88     quick_pow(2,2147482,2147481);
89     package_all();
90     package01();
91 }