GCD XOR, ACM/ICPC Dhaka 2013, UVa12716

不同的枚举方法，效率完全不同。值得记录一下！

 1 #include <cstdio>
 2 #include <cstring>
 3 int t, a, b, c, n, cas = 0, count = 0;
 4 int cnt[30000000];
 5 void pre() {
 6     count = 0;
 7     memset(cnt, 0, sizeof(cnt));
 8
 9     for (a = 1; a <= 30000000; a++) {
10         for (c = 1; c < a; c++) {
11             if (a%c == 0 && ((a-c)^a)==c) {
12                 count++;
13             }
14         }
15         cnt[a-1] = count;
16     }
17
18 }
19 int main(void)
20 {
21
22     for (scanf("%d", &t); t--;) {
23         scanf("%d", &n);
24         printf("Case %d: %d\n", ++cas, cnt[n-1]);
25     }
26     return 0;
27 }

View Code

 1 #include <cstdio>
 2 #include <cstring>
 3 int t, a, b, c, n, cas = 0, count = 0;
 4 const int maxn = 30000000;
 5 int cnt[maxn];
 6 void pre() {
 7     count = 0;
 8     memset(cnt, 0, sizeof(cnt));
 9
10     for (c = 1; c <= maxn/2; c++) {
11         for (a = c+c; a <= maxn; a+=c) {
12             if (((a-c)^a)==c) {
13                 cnt[a]++;
14             }
15         }
16     }
17     for (int i = 1; i <= maxn; i++) {
18         cnt[i] += cnt[i-1];
19     }
20
21 }
22 int main(void)
23 {
24     pre();
25     for (scanf("%d", &t); t--;) {
26         scanf("%d", &n);
27         printf("Case %d: %d\n", ++cas, cnt[n]);
28     }
29     return 0;
30 }

View Code