public class ExMath {
 public static boolean isPrime(int x) {
 if (x == 1) return false;
 if (x == 2 || x == 3) return true;
 if (x % 2 == 0) return false;
 for (int i = 3; i <= Math.sqrt(x + 1); i += 2) {
 if (x % i == 0) return false;
 }
 return true;
 }

 //动态规划求斐波那契数
 //T=O(N)
 public static long fibonacci_dp(int n) {
 //f(0)=f(1)=1
 if (n <= 1) return 1;
 long last = 1, nextToLast = 1, answer = 1;
 for (int i = 2; i <= n; i++) {
 answer = last + nextToLast;
 nextToLast = last;
 last = answer;
 }
 return answer;
 }

 public static long dec2Bi(int x) {
 int remainder = x;
 long ret = 0;
 int level = 0;
 while (remainder != 0) {
 ret += (long) remainder % 2 * Math.pow(10, level++);
 remainder /= 2;
 }
 return ret;
 }

 public static int min(int a, int b, int c) {
 int ret = a;
 if (ret > b) ret = b;
 if (ret > c) ret = c;
 return ret;
 }

 //求两个正整数的最大公因数
 public static int gcd(int a, int b) {
 if (a < b) {
 int tmp = a;
 a = b;
 b = tmp;
 }
 int remainder = a % b;
 while (remainder != 0) {
 a = b;
 b = remainder;
 remainder = a % b;
 }
 return b;
 }

 //求三个正整数的最大公因数
 public static int gcd(int a, int b, int c) {
 //求多个数的最大公因数:多次辗转相除法
 //先求a,b的最大公因数gcd(a,b),再求gcd(a,b)与c的最大公因数
 int tmp = gcd(a, b);
 return gcd(tmp, c);
 }

 public static long fibonacci(int n) {
 if (n == 1 || n == 2) return 1;
 else return fibonacci(n - 1) + fibonacci(n - 2);
 }

 public static long fact(int n) {
 if (n < 0) return 0;
 if (n == 0 || n == 1) return 1;
 else return n * fact(n - 1);
 }
}