luogu P1214 等差数列枚举

 1 //打出表可以看到，集合内有大约cnt=120000个数。做法是枚举等差数列前两个数，然后再用一个N去判断序列后面每一位是否存在。复杂度高达cnt^2*n，加了玄学优化可以过，应该不是正解。 
 2 #include <cstdio>
 3 #include <vector>
 4 #include <algorithm>
 5 using namespace std;
 6 vector <int> vec;
 7 int n,m;
 8 int vis[130000];
 9 struct dat
10 {
11     int a,b;
12     dat(int _a = 0,int _b = 0):a(_a),b(_b){}
13     friend bool operator < (dat x,dat y)
14     {
15         if (x.b != y.b)
16             return x.b < y.b;
17         return x.a < y.a; 
18     }
19 };
20 vector <dat> ans;
21 int main()
22 {
23     scanf("%d%d",&n,&m);
24     for (int i = 0;i <= m;i++)
25         for (int j = i;j <= m;j++)
26             vis[i * i + j * j] = true;
27     for (int i = 0;i <= 125000;i++)
28         if (vis[i] == true)
29             vec.push_back(i);
30     for (int i = 0;i < vec.size();i++)
31         for (int j = i + 1;j < vec.size();j++)
32         {
33             int a = vec[i],b = vec[j] - vec[i];
34             //玄学剪枝 
35             if (a + (n - 1) * b > vec[vec.size() - 1])
36                 break;
37             int cnt = 1;
38             while (vis[a + cnt * b] == true && cnt < n)
39                 cnt++;
40             if (cnt == n)
41                 ans.push_back(dat(a,b));
42         }
43     if (ans.size() == 0)
44     {
45         printf("NONE
");
46         return 0;
47     }
48     sort(ans.begin(),ans.end());
49     for (int i = 0;i < ans.size();i++)
50         printf("%d %d
",ans[i].a,ans[i].b);
51     return 0;
52 }
心之所动且就随缘去吧
luogu P1214 等差数列 枚举

luogu P1214 等差数列枚举
