Mathematics for Topcoders

Primes

优化1：比较范围只需要限制在sqrt(n)

优化2：偶数不存在质数（除了2），所以对从3开始check的时候，可以一次加2，而不是加1，也就是说只check奇数的因子。

如果只是这样的话，生成一个比较大范围的质数还是比较慢的，因为很多数计算了多次。

因此我们采用Sieve of Eratosthenes方法，思想很简单，将质数的倍数删掉，剩下的就是质数。

bool* sieve(int n){
  bool* prime = new bool[n+1];
  for(int i=0; i<=n; i++){
    prime[i] = true;
  }
  prime[0] = false;
  prime[1] = false;
  int m = sqrt(n);
  
  for(int i=2; i<=m; i++){
    if(prime[i]){
      for(int k=i*i; k<=n; k+=i){
        prime[k] = false;
      }
    }
  }
  return prime;
}

GCD

最简单的算法，就是从俩个数的较小的数开始，然后逐次减1.

还有另一个更快的算法，Euclid’s algorithm,(其实就是我们说的辗转相除)

具体到代码上就是：

int GCD(int a, int b){
  if(b==0) return a;
  return GCD(b, a%b);
}

有了GCD的代码，求最小公倍数也就很简单了

1
2
3

int LCM(int a, int b){
  return b*a/GCD(a,b);
}

Geometry

矩形相交的计算：这里一个点就是如何表示一个矩形，一般是存储左下以及右上。那么intersection就是max(x1,x3),max(y1,y3)和min(x2,x4),min(y2,y4)。之后再比较左下和右上的关系就可以确定到底有没有相交了。
如何计算多边形相交的lattice points. Pick’s algorithm
2. 公式是： Area= B/2 + i - 1, B是绿点数，i是红点数

欧拉公式（Euler’s formula)
1. V-E+F = 2, V是顶点数，E是边数，F是面数，一个正方形，俩条对角线相连，V是5， E是8， F是5，最外头也算一个面。

Bases

进制问题。

其他进制转10进制：就是将每位数字乘以进制之后相加。

int toDecimal(int n, int base){
  int multi = 1;
  int result = 0;
  while(n>0){
    result += n%base * multi;
    multi *= base;
    n = n/10;
  }
  return result;
}

10进制转其他进制，小于10的: 这个就是除以对应进制，之后的余数逆序即可

int fromDecimal(int n, int base){
  int multi=1;
  int res = 0;
  while(n>0){
    res += n%base * multi;
    multi *= 10;
    n = n/base;
  }
  return res;
}

以及从10进制转到11-20

int fromDecimal2(int n, int base){
  string chars="0123456789ABCDEFGHIJ";
  string res="";
  while(n>0){
    res = chars[n%base] + res;
    n = n / base;
  }
  return res;
}

Fractions and Complex Numbers

这个主要是表示问题，当然可以自定义相应的类。但实际中，可以使用pair来完成存储，更加简单快捷。