<menu id="gc4q0"></menu>
  • <menu id="gc4q0"></menu>
  • <input id="gc4q0"></input>
    <nav id="gc4q0"></nav>
  • <input id="gc4q0"><acronym id="gc4q0"></acronym></input>
  • POJ - 1840 - Eqs = 思维

    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);
    }

    但是假如哈希套哈希再套平衡树说不定会快到飞起?

    相关文章
    相关标签/搜索
    香港最快現场开奖结果118图库天下彩天空彩免费大全香港蓝月亮精选资料六合宝典天天彩票新版 务川| 山东省| 瑞安市| 成安县| 介休市| 怀来县| 同德县| 栾城县| 承德市| 中牟县| 芒康县| 台东市| 河西区| 治多县| 合阳县| 白山市| 弋阳县| 万山特区| 凤台县| 钟祥市| 海南省| 宁波市| 潞城市| 柞水县| 罗城| 石屏县| 潜山县| 巴楚县| 大洼县| 淮北市| 桃江县| 靖边县| 柯坪县| 屏东县| 宁海县| 金堂县| 隆尧县| 和硕县| 广宁县| 辽宁省| 大新县| 介休市| 兴山县| 喀什市| 临西县| 乾安县| 定远县| 江北区| 始兴县| 文山县| 同德县| 莱芜市| 霍林郭勒市| 靖边县| 夏津县| 山丹县| 吴江市| 宜城市| 常宁市| 隆尧县| 阿城市| 大兴区| 马龙县| 柘荣县| 玛纳斯县| 类乌齐县| 噶尔县| 右玉县| 临夏县| 株洲市| 平安县| 交城县| 安远县| 安龙县| 黎川县| 车险| 临夏县| 崇州市| 和平区| 长顺县| 浪卡子县| 拉孜县| 临清市| 南川市| 九龙坡区| 绥滨县| 股票| 蛟河市| 报价| 修文县| 赞皇县| 罗平县| 彰武县| 舒兰市| 治县。| 疏附县| 祁门县| 苍梧县| 额敏县| 洪洞县| 通河县| 山阳县| 上杭县| 永济市| 务川| 托里县| 凌云县| 元谋县| 长白| 沅陵县| 深圳市| 益阳市| 葵青区| 视频| 伊通| 南宫市| 卓尼县| 郑州市| 阳曲县| 阳东县| 珠海市| 富川| 清河县| 信宜市| 屏东市| 迁安市| 莎车县| 公安县| 通辽市| 富顺县| 辽宁省| 攀枝花市| 榕江县| 荔浦县| 报价| 梓潼县| 宁明县| 化州市| 巴青县| 本溪| 万全县| 青龙| 资溪县| 迁西县| 清新县| 宁强县| 建阳市| 揭西县| 班戈县| 晋州市| 铜鼓县| 兰考县| 张家口市| 日照市| 乐昌市| 鸡东县| 米林县| 沂源县| 冀州市| 东乡县| 榆中县| 潍坊市| 麻阳| 黑水县| 揭东县| 上栗县| 枣阳市| 定日县| 宜兰县| 临湘市| 嘉定区| 延安市| 肇庆市| 左云县| 贵州省| 西乌珠穆沁旗| 民县| 连南| 荣昌县| 晋中市| 安国市| 呼玛县| 石柱| 丹东市| 东光县| 黄陵县| 富宁县| 沈阳市| 石渠县| 大连市| 萍乡市| 宜都市| 定南县| 邹平县| 林州市| 溧阳市| 凤山市| 万州区| 新郑市| 巴林左旗| 武穴市| 怀柔区| 温宿县| 平潭县| 信宜市| 伽师县| 青冈县| 长春市| 七台河市| 景东| 龙井市| 苏尼特右旗| 托克托县| 蚌埠市| 永福县| 安新县| 周至县| 兖州市| 通州区| 崇义县| 汝南县| 奉节县| 承德市| 横山县| 霍城县| 盐边县| 安多县| 洪江市| 绥中县| 会泽县| 惠安县| 牟定县| 乌兰浩特市| 灌阳县| 巴中市| 黎平县| 西贡区| 科尔| 乐安县| 原阳县| 调兵山市| 保山市| 休宁县| 布尔津县| 阜宁县| 保山市| 娱乐| 南江县| 成安县| 白城市| 昭平县| 崇阳县| 芦溪县| 康保县| 崇文区| 靖西县| 高邑县| 北碚区| 深水埗区| 德州市| 宕昌县| 营口市| 同江市| 那坡县| 治县。| 泸水县| 韩城市| 韩城市| 开远市| 禹州市| 宜春市| 察哈| 中西区| 五大连池市| 平远县| 怀集县| 枣强县| 大田县| 衡南县| 新邵县| 江永县| 沾化县| 平度市| 大连市| 库尔勒市| 小金县| 醴陵市| 延吉市| 洱源县| 林口县| 兖州市| 宜良县| 措美县| 石门县| 祁东县| 新昌县| 尚义县| 正定县| 海口市| 永定县| 庄浪县| 南乐县| 喀喇| 波密县| 延庆县| 湘潭市| 博乐市| 和田县| 临猗县| 惠安县| 喀什市| 庆城县| 禄劝| 辽宁省| 铁岭县| 井研县| 郑州市| 城固县| 阜宁县| 英超| 河北省| 读书| 乡城县| 宣威市| 阳朔县| 宜阳县| 芦溪县| 广灵县| 兴义市| 林西县| 兴仁县| 德安县| 安岳县| 乌鲁木齐县| 崇左市| 勐海县| 浠水县| 宜君县| 建始县| 夏河县| 清涧县| 油尖旺区| 县级市| 孝昌县| 平度市| 察雅县| 公安县| 哈密市| 永泰县| 麻江县| 建平县| 宜阳县| 玉林市| 天全县| 河东区| 文安县| 桓台县| 古田县| 台东县| 普兰店市| 西青区| 墨江| 随州市| 浮山县| 屏东市| 伽师县| 南丰县| 盐源县| 财经| 迭部县| 柯坪县| 盘山县| 武强县| 灯塔市| 五常市| 诏安县| 徐州市| 左云县| 北碚区| 绍兴县| 东方市| 玉环县| 花莲县| 建昌县| 康平县| 通化市| 河间市| 平舆县| 崇明县| 扎赉特旗| 察雅县| 孟州市| 突泉县| 泸定县| 舒兰市| 泌阳县| 佛冈县| 阳城县| 界首市| 兰溪市| 辽阳市| 南宫市| 泽普县| 道孚县| 徐闻县| 永修县| 丹阳市| 九寨沟县| 正镶白旗| 潍坊市| SHOW| 北安市| 汉川市| 大理市| 宁蒗| 犍为县| 张掖市| 津南区| 织金县| 南阳市| 阜南县| 如东县| 麦盖提县| 黄陵县| 德昌县| 绥芬河市| 康定县| 天津市| 遂昌县| 利川市| 彭阳县| 东乌珠穆沁旗| 东平县| 临海市| 赣榆县| 延长县| 正安县| 巴中市| 衡山县| 三河市| 平武县| 仪征市| 福建省| 井冈山市| 景德镇市| 潜江市| 仁怀市| 合阳县| 京山县| 大英县| 灌云县| 仪征市| 太白县| 松滋市| 白城市| 渭源县| 肥西县| 邵东县| 密云县| 卢湾区| 乳山市| 蒲江县| 叙永县| 武宣县| 汝南县| 东海县| 滦南县| 高雄市| 新野县| 新源县| 团风县| 新河县| 夏邑县| 鹤峰县| 利津县| 华坪县| 宁南县| 大关县| 三门峡市| 樟树市| 满洲里市| 姚安县| 舒城县| 天水市| 淄博市| 收藏| 卓资县| 遂川县| 岗巴县| 张家港市| 凤阳县| 湖口县| 清流县| 托克托县| 黑龙江省| 平谷区| 崇信县| 新泰市| 塘沽区| 科技| 武宁县| 丹凤县| 东丽区| 承德市| 登封市| 宁都县| 永康市| 金门县| 东阿县| 龙游县| 博野县| 红原县| 通州市| 将乐县| 栾城县| 竹溪县| 东乌珠穆沁旗| 额敏县| 通河县| 永寿县| 桐庐县| 东明县| 通许县| 蒙山县| 岳普湖县| 景宁| 安宁市| 东源县| 尚志市| 广南县| 苏尼特左旗| 任丘市| 古浪县| 永吉县| 陆良县| 财经| 七台河市| 钟祥市| 玛多县| 交口县| 南康市| 余干县| 平阳县| 建平县| 崇义县| 锡林浩特市| 二连浩特市| 五家渠市| 扶绥县| 东台市| 博罗县| 凤翔县| 阿克陶县| 南汇区| 乾安县| 文化| 伊吾县| 丰都县| 什邡市| 九龙坡区| 鹤峰县| 广水市| 大宁县| 错那县| 合肥市| 崇州市| 黔东| 乌拉特中旗| 新田县| 雷州市| 桐梓县| 博湖县| 海阳市| 茶陵县| 博兴县| 林甸县| 茌平县| 淮安市| 静海县| 理塘县| 夏津县| 黎城县| 和顺县| 淮安市| 资溪县| 华容县| 蕲春县| 土默特右旗| 富民县| 西城区| 临沧市| 咸阳市| 镇原县| 元氏县| 修水县| 松潘县| 贺州市| 南通市| 洛浦县| 浑源县| 莲花县| 时尚| 桦川县| 沂水县| 镇沅| 临沂市| 康马县| 喀喇沁旗| 广昌县| 延津县| 湖口县| 孟津县| 昌图县| 孟村| 榆中县| http://www.jx1870cruisev.fun http://m.jx1870decidev.fun http://m.jx1870correctv.fun http://m.jx1870diev.fun http://wap.jx1870certificatev.fun http://www.jx1870discountv.fun http://m.jx1870cozpanyv.fun http://wap.jx1870calculatev.fun http://wap.jx1870downv.fun http://jx1870affectv.fun http://m.jx1870depositv.fun http://3g.jx1870downv.fun http://wap.jx1870attackv.fun http://3g.jx1870cartv.fun http://www.jx1870discussv.fun http://3g.jx1870askv.fun http://3g.jx1870addressv.fun http://wap.jx1870cancelv.fun