http://poj.org/problem?id=1840 题意:求 \(a_1x_1^3+a_2x_2^3+a_3x_3^3+a_4x_4^3+a_5x_5^3=0\) 的整数解,其中所有变量的取值都是 \([-50,50]\) ,且 \(x_i \neq 0\) 暴力枚举,但是要怎么分两半呢?事实证明是前
http://poj.org/problem?id=1840
题意:求 \(a_1x_1^3+a_2x_2^3+a_3x_3^3+a_4x_4^3+a_5x_5^3=0\) 的整数解,其中所有变量的取值都是 \([-50,50]\) ,且 \(x_i \neq 0\)
暴力枚举,但是要怎么分两半呢?事实证明是前半部分分2个,后半部分分3个会更好,为什么呢?
大概是多了一个 \(\log_{2}{100}\)吧,也是差不多7倍常数了。
前半部分分两个是:
\(O(n^2\log(n^2)+n^3\log(n^2))\)
前半部分分三个就白白多了7倍常数,实属逗比。
可惜POJ用不了unordered_map,待会手写一发hash看看?
#include<algorithm> #include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<map> #include<set> #include<stack> #include<string> #include<queue> #include<vector> using namespace std; typedef long long ll; map<int, int> M; int main() { #ifdef Yinku freopen("Yinku.in", "r", stdin); #endif // Yinku int a1, a2, a3, a4, a5; scanf("%d%d%d%d%d", &a1, &a2, &a3, &a4, &a5); for(int x1 = -50; x1 <= 50; ++x1) { if(x1 == 0) continue; int p1 = a1 * x1 * x1 * x1; for(int x2 = -50; x2 <= 50; ++x2) { if(x2 == 0) continue; int p2 = a2 * x2 * x2 * x2; M[p1 + p2]++; } } ll ans = 0; for(int x3 = -50; x3 <= 50; ++x3) { if(x3 == 0) continue; int p3 = a3 * x3 * x3 * x3; for(int x4 = -50; x4 <= 50; ++x4) { if(x4 == 0) continue; int p4 = a4 * x4 * x4 * x4; for(int x5 = -50; x5 <= 50; ++x5) { if(x5 == 0) continue; int p5 = a5 * x5 * x5 * x5; map<int, int>::iterator it = M.find(-p3 - p4 - p5); if(it != M.end()) ans += it->second; } } } printf("%lld\n", ans); }
一个假的哈希,大概就是把它按余数分裂成几棵平衡树来减小树的规模,大概取值合理的话可以快3倍左右(原本平衡树应该是 \(\log_2{10^6}=20\) 的,套个余数哈希(余数为 \(5\times10^4\) )就快了三倍,大概符合 \(\log_2{10^2}=7\) ),注意初始化map是需要时间的,所以并不是余数取越大越好,而且的确会创建map的实例,占用内存空间。
#include<algorithm> #include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<map> #include<set> #include<stack> #include<string> #include<queue> #include<vector> using namespace std; typedef long long ll; const int MAXN = 49999; struct HashTable { map<int, int> M[MAXN]; void insert(int x) { int p = x % MAXN; if(p < 0) p += MAXN; M[p][x]++; } int count(int x) { int p = x % MAXN; if(p < 0) p += MAXN; map<int, int>::iterator it = M[p].find(x); if(it != M[p].end()) return it->second; return 0; } } ht; //寻找n以内的一个最大的质数 /*const int MAXP=2e6; bool np[MAXP+1]; void find_p(int n){ np[1]=1; for(int i=1;i<=n;++i){ if(np[i]) continue; for(int j=i+i;j<=n;j+=i) np[j]=1; } for(int i=n;;--i){ if(!np[i]){ printf("MAXP=%d\n",i); break; } } }*/ int main() { #ifdef Yinku freopen("Yinku.in", "r", stdin); #endif // Yinku //find_p(5e4); int a1, a2, a3, a4, a5; scanf("%d%d%d%d%d", &a1, &a2, &a3, &a4, &a5); for(int x1 = -50; x1 <= 50; ++x1) { if(x1 == 0) continue; int p1 = a1 * x1 * x1 * x1; for(int x2 = -50; x2 <= 50; ++x2) { if(x2 == 0) continue; int p2 = a2 * x2 * x2 * x2; ht.insert(p1 + p2); } } ll ans = 0; for(int x3 = -50; x3 <= 50; ++x3) { if(x3 == 0) continue; int p3 = a3 * x3 * x3 * x3; for(int x4 = -50; x4 <= 50; ++x4) { if(x4 == 0) continue; int p4 = a4 * x4 * x4 * x4; for(int x5 = -50; x5 <= 50; ++x5) { if(x5 == 0) continue; int p5 = a5 * x5 * x5 * x5; ans += ht.count(-p3 - p4 - p5); } } } printf("%lld\n", ans); }
但是假如哈希套哈希再套平衡树说不定会快到飞起?