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公式