2009年11月10日星期二.sgu116 sgu117 sgu118 pku2850

2009年11月10日星期二
首先線性的素數篩法是這么寫的

memset(is_prime,1,sizeof(is_prime));
is_prime[1] = 0;
cnt = 0;
for(i = 2;i < M;i++) {
    if(is_prime[i]) prime[cnt++] = i;
    for(j = 0;j < cnt && i * prime[j] < M;j++) {
        is_prime[i * prime[j]] = 0;
        if(i % prime[j] == 0) break;
    }
}


sgu 118:
1.數學處理之，分解成A1( 1 + A2(1 + A3(1 + A4(......An-1(1 + An))))
2.把數字寫出來找規律.
int root(int x)
{
    int sum = 各位數字和;
    if(sum >= 10)
        return root(sum);
    return sum;
    
}
等價于
int root(int x)
{
    if(x % 9) return x % 9;
    return 9;
}


sgu 117:因數分解，比較大小。
    faccnt = 0;
    for(i = 0;K > 1 && i < top;i++) {
        if(K % prime[i] == 0) {
            idx[faccnt++] = i; //tle hint : jump idx
        }
        while(K % prime[i] == 0) {
            fac[i] ++;
            K /= prime[i];
        }
    }

sgu 116:篩法求素數，然后背包，我WA了10幾次，
發現題目雖然要求不降序，but,but!!我把結果排序輸出的，然后狂WA
去了就OK了。

pku 2850:數學或者幾何
沒有trcik ，會求兩個圓上搭的圓的圓心即可。可以考慮heron公式

posted on 2009-11-10 21:23 schindlerlee 閱讀(1374) 評論(1)  編輯 收藏 引用 所屬分類: 解題報告