• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            Why so serious? --[NKU]schindlerlee

            2009年12月21日星期一.sgu499

            2009年12月21日星期一.sgu499
            注:此文包括線性篩法,質因子分解,dfs生成一個數的所有因子

            sgu499:我想撞墻
            http://m.shnenglu.com/schindlerlee/
            那天arxor看我和angelclover在做,然后也在看題,這個題我還沒看,然后arxor大牛就給我說了個想法

            把每個數分解素因子,然后dfs出這個數的所有因子。
            對每個數進行一次此操作,最后找最大的且被訪問了兩邊以上的因子,
            但是這個方法tle在test 20了。怪我當時沒細想,被大牛隨便一說就覺得這個方法很好。。。。然后。。。杯具了

            上代碼:tle@20
             1 /*
             2  * SOUR:sgu Greatest Greatest Common Divisor
             3  * ALGO:因子分解
             4  * DATE: 2009年 12月 20日 星期日 19:24:49 CST
             5  * COMM:3http://m.shnenglu.com/schindlerlee/
             6  * */
             7 #include<iostream>
             8 #include<cstdio>
             9 #include<cstdlib>
            10 #include<cstring>
            11 #include<algorithm>
            12 using namespace std;
            13 typedef long long LL;
            14 const int maxint = 0x7fffffff;
            15 const long long max64 = 0x7fffffffffffffffll;
            16 
            17 const int N = 1000010;
            18 int vis[N], n, is_prime[N], primes[N], top;
            19 int exp[100], num[100], cnt;
            20 int can[N];
            21 void generate()
            22 {
            23     int i, j, k;
            24     top = 0;
            25     fill(is_prime, is_prime + N, 1);
            26     for (i = 2; i <= 1000000; i++) {
            27         if (is_prime[i]) {
            28             primes[top++= i;
            29         }
            30         for (j = 0; j < top && i * primes[j] <= 1000000; j++) {
            31             is_prime[i * primes[j]] = 0;
            32             if (i % primes[j] == 0)
            33                 break;
            34         }
            35     }
            36     //for(i = 0;i < top;i++) {
            37     //printf("%d\n",primes[i]);
            38     //}
            39 }
            40 
            41 void factor(int x)
            42 {
            43     //printf("factor %d\n",x);
            44     cnt = 0;
            45     for (int i = 0; i < top && x > 1; i++) {
            46         if (x % primes[i] == 0) {
            47             //printf("primes[i] = %d\n",primes[i]);
            48             can[i]++;
            49             num[cnt] = primes[i];
            50             exp[cnt] = 0;
            51             while (x % primes[i] == 0) {
            52                 exp[cnt]++;
            53                 x /= primes[i];
            54             }
            55             cnt++;
            56         }
            57     }
            58 }
            59 
            60 void dfs(int x, int level)
            61 {
            62     if (level == cnt) {
            63         //printf("dfs x= %d\n",x);
            64         vis[x]++;
            65         return;
            66     }
            67     dfs(x, level + 1);
            68     for (int i = 1; i <= exp[level]; i++) {
            69         x *= num[level];
            70         dfs(x, level + 1);
            71     }
            72 }
            73 
            74 int main()
            75 {
            76     int i, j, k;
            77     generate();
            78     scanf("%d"&n);
            79     for (i = 0; i < n; i++) {
            80         scanf("%d"&k);
            81         factor(k);
            82         dfs(10);
            83     }
            84     for (i = N - 1; i >= 0; i--) {
            85         if (vis[i] >= 2) {
            86             printf("%d\n", i);
            87             break;
            88         }
            89     }
            90     return 0;
            91 }
            92 

            然后比賽完google了以下,原來是水題,不予解釋了,貼代碼
             1 
             2 const int N = 1000010;
             3 int vis[N],n,m;
             4 void chkmax(int &x,int k) { if(x < k) x = k; }
             5 int main()
             6 {
             7     int i,j,k;
             8     scanf("%d",&n);
             9     for(i = 0;i < n;i++) {
            10         scanf("%d",&k);
            11         vis[k] ++;
            12         chkmax(m,k);
            13     }
            14 
            15     int res = 1;
            16     for(i = 2;i <= m;i++) {
            17         int tmp = 0;
            18         for(j = i;tmp < 2 && j <= m;j += i) {
            19             tmp += vis[j];
            20         }
            21         if(tmp >= 2) res = i;
            22     }
            23     printf("%d\n",res);
            24
            25     return 0;
            26 }
            27 
            28 

            結果第二天arxor,說他用那個方法過了。。。。。。。。。
            然后我看了他的代碼,我發現原來我的因子分解是沒有優化的。。。
            然后把第45行改成
                for (int i = 0; primes[i] * primes[i] <= x && i < top && x > 1; i++) {

            過了。。。。。

            posted on 2009-12-21 20:54 schindlerlee 閱讀(1093) 評論(0)  編輯 收藏 引用 所屬分類: 解題報告

            99久久香蕉国产线看观香| 久久青青草原国产精品免费| 一本色道久久88综合日韩精品 | 99久久国产热无码精品免费| 久久精品国产第一区二区三区| 久久综合久久综合久久| 久久亚洲熟女cc98cm| 久久亚洲日韩精品一区二区三区 | 熟妇人妻久久中文字幕| 色综合久久综精品| 久久久久久久97| 精品久久久久久无码人妻热| 亚洲伊人久久大香线蕉综合图片| 91精品国产综合久久久久久| 女人高潮久久久叫人喷水| 久久福利青草精品资源站免费| 亚洲国产精品成人久久蜜臀| 久久国产精品久久久| 日韩久久久久久中文人妻| 性做久久久久久久久| 岛国搬运www久久| 777米奇久久最新地址| 狠狠色婷婷久久一区二区 | 久久www免费人成看国产片| 国产亚洲精久久久久久无码| 久久精品成人欧美大片| 三级片免费观看久久| 久久99久久无码毛片一区二区| 99久久国产热无码精品免费| 久久精品亚洲中文字幕无码麻豆 | 久久亚洲精品中文字幕三区| 99久久国语露脸精品国产| 久久久久波多野结衣高潮| 欧美久久天天综合香蕉伊| 久久精品国产99国产精品| 国产精品99久久不卡| 国产一区二区三精品久久久无广告| 激情伊人五月天久久综合| 国产精品无码久久久久久| 99999久久久久久亚洲| 久久99国产精品二区不卡|