枚举题。
1 #include < iostream > 2 #include < string > 3 #include < algorithm > 4 #include < string .h > 5 #include < vector > 6 #include < math.h > 7 #include < time.h > 8 #include < queue > 9 #include < set > 10 using namespace std; 11 12 const int MAX = 125005 ; 13 14 struct NODE 15 { 16 int a, b; 17 NODE( int aa, int bb) : a(aa), b(bb) {} 18 NODE() {} 19 bool operator < ( const NODE & t) const 20 { 21 if (b != t.b) return b < t.b; 22 else return a < t.a; 23 } 24 }; 25 26 set < int > num; 27 vector < NODE > ans; 28 29 bool use[MAX]; 30 int n, m; 31 32 void ready() 33 { 34 memset(use, false , sizeof (use)); 35 for ( int i = 0 ; i <= m; i ++ ) 36 { 37 for ( int j = 0 ; j <= m; j ++ ) 38 { 39 use[i * i + j * j] = true ; 40 num.insert(i * i + j * j); 41 } 42 } 43 } 44 45 int getMaxD( int a, int b) 46 { 47 return (b - a) / (n - 1 ) + 1 ; 48 } 49 50 int getMaxNum() 51 { 52 int res = - 1 ; 53 set < int > ::iterator it; 54 for (it = num.begin(); it != num.end(); it ++ ) 55 { 56 res = max(res, * it); 57 } 58 return res; 59 } 60 61 void go() 62 { 63 // 枚举起点 64 set < int > ::iterator it; 65 int maxNum = getMaxNum(); 66 for (it = num.begin(); it != num.end(); it ++ ) 67 { 68 int beg = * it; 69 int i, j; 70 // 枚举公差 71 int d = getMaxD(beg, maxNum); 72 for (i = 1 ; i <= d; i ++ ) 73 { 74 // 判是否够长 75 for (j = 0 ; j < n; j ++ ) 76 { 77 if (use[beg + i * j] == false ) break ; 78 } 79 if (j >= n) ans.push_back(NODE(beg, i)); 80 } 81 } 82 if (ans.size() == 0 ) 83 { 84 printf( " NONE\n " ); 85 return ; 86 } 87 sort(ans.begin(), ans.end()); 88 for ( int i = 0 ; i < ans.size(); i ++ ) 89 { 90 printf( " %d %d\n " , ans[i].a, ans[i].b); 91 } 92 } 93 94 int main() 95 { 96 freopen( " ariprog.in " , " r " , stdin); 97 freopen( " ariprog.out " , " w " , stdout); 98 99 scanf( " %d%d " , & n, & m); 100 ready(); 101 go(); 102 }
转载于:https://www.cnblogs.com/litstrong/archive/2010/04/12/1710548.html
