多种方法过Codeforces Round #270的A题（奇偶法、打表法和Miller

多种方法过Codeforces Round #270的A题（奇偶法、打表法和Miller_Rabin（这个方法才是重点））

题目链接：http://codeforces.com/contest/472/problem/A

题目：

题意：哥德巴赫猜想是：一个大于2的素数一定可以表示为两个素数的和。此题则是将其修改为：一个大于等于12的数一定能表示为两个合数的和。

思路：这个很容易，下面是三种方法的代码。

奇偶法：一个数要么是奇数要么是偶数，众所周知大于2的偶数都是合数（因为都能被2整除嘛），所以只要把该数分解为两个非2的偶数的和即可。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long 
 4 #define pb push_back
 5 #define mem(a,b) memset(a,b,sizeof(a))
 6 
 7 int main()
 8 {
 9     ios::sync_with_stdio(false);
10     cin.tie(0);
11     int n;
12     cin>>n;
13     if(n%2==0)cout<<4<<' '<<n-4<<endl;
14     else cout<<9<<' '<<n-9<<endl;
15     return 0;    
16 }

打表法：将素数筛出来，然后进行遍历即可。

 1 #include <iostream>
 2 using namespace std;
 3 
 4 const int maxn = 1e6 + 7;
 5 int n;
 6 int p[maxn];
 7 
 8 void init() {
 9     for(int i = 2; i < maxn; i++) {
10         p[i] = 1;
11     }
12     for(int i = 2; i * i < maxn; i++) {
13         if(p[i]) {
14             for(int j = i * i; j < maxn; j += i) {
15                 p[j] = 0;
16             }
17         }
18     }
19 }
20 
21 int main() {
22     init();
23     cin >>n;
24     for(int i = n / 2; i >= 1; i--) {
25         if(!p[i] && !p[n - i]) {
26             cout <<i <<" " <<n - i <<endl;
27             return 0;
28         }
29     }
30     return 0;
31 }

Miller_Rabin法：这个是关键，其实这种方法的思路和上一种方法一样，不过不是打表，而是用Miller_Rabin来判断是否为素数，最重要的是Miller_Rabin法可以判断大素数，而打表却不可以！！！（计蒜客上一题也是用这个方法，且是大数据，打表不可过，链接为：https://nanti.jisuanke.com/t/25985，这个题的题解链接为https://www.cnblogs.com/Dillonh/p/9301991.html).

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 typedef long long ll;
 5 int n;
 6 
 7 ll multi(ll a, ll b, ll mod) {
 8     ll ret = 0;
 9     while(b) {
10         if(b & 1)
11             ret = ret + a;
12         if(ret >= mod)
13             ret -= mod;
14 
15         a = a + a;
16         if(a >= mod)
17             a -= mod;
18         b >>= 1;
19     }
20     return ret;
21 }
22 ll quick_pow(ll a, ll b, ll mod) {
23     ll ret = 1;
24     while(b) {
25         if(b & 1)
26             ret = multi(ret, a, mod);
27         a = multi(a, a, mod);
28         b >>= 1;
29     }
30     return ret;
31 }
32 bool Miller_Rabin(ll n) {
33     ll u = n - 1, pre, x;
34     int i, j, k = 0;
35     if(n == 2 || n == 3 || n == 5 || n == 7 || n  == 11)
36         return true;
37     if(n == 1 || (!(n % 2)) || (!(n % 3)) || (!(n % 5)) || (!(n % 7)) || (!(n % 11)))
38         return false;
39     for(; !(u & 1); k++, u >>= 1);
40     srand(time(NULL));
41     for(i = 0; i < 5; i++) {
42         x = rand() % (n - 2) + 2;
43         x = quick_pow(x, u, n);
44         pre = x;
45         for(j = 0; j < k; j++) {
46             x = multi(x, x, n);
47             if(x == 1 && pre != 1 && pre != (n - 1))
48                 return false;
49             pre = x;
50         }
51         if(x != 1)
52             return false;
53     }
54     return true;
55 }
56 
57 
58 int main() {
59     cin >>n;
60     for(int i = n / 2; i >= 1; i--) {
61         if(!Miller_Rabin(i) && !Miller_Rabin(n - i)) {
62             cout <<i <<" " <<n - i <<endl;
63             return 0;
64         }
65     }
66     return 0;
67 }