2014年10月24日 20:32

Kim Jaeju

edited: 2014年10月24日 21:02

Java. long자료형을 사용했더니, 100000을 입력했더니 음수가 결과값으로 나오는 오류가 발생하네요 ᅲᅲ.. 도와주실분?

package h_Fibonacci2;
import java.util.Scanner;
public class Secret {
 public static void main(String[] args) {
 Scanner in=new Scanner(System.in);
 System.out.println("Input:");
 long n=in.nextLong();
 long i,a=0l, b=1l, temp=0l, c=4294967291l;
 for(i=1l;i<n;i++){
 temp=a;
 a+=b;
 b=temp; 
 }
 System.out.println("Output:"+(a%c));
 }
}

Input:
100000
Output:-3809483798

package rootcucu.codefight;
import java.math.BigDecimal;
public class FibonacciModulo {
 public static class Matrix {
 public final static Matrix ADVANCE[] = new Matrix[]{
 new Matrix(1,0,0,1),
 new Matrix(1,1,1,0),
 new Matrix(2,1,1,1),
 new Matrix(3,2,2,1),
 new Matrix(5,3,3,2),
 new Matrix(8,5,5,3),
 new Matrix(13,8,8,5),
 };
 public static Matrix IDENTITY = new Matrix(1,0,0,1);
 private BigDecimal a, b, c, d;
 Matrix(BigDecimal a, BigDecimal b, BigDecimal c, BigDecimal d){
 this.a = a;
 this.b = b;
 this.c = c;
 this.d = d;
 }
 Matrix(int a, int b, int c, int d){
 this.a = new BigDecimal(a);
 this.b = new BigDecimal(b);
 this.c = new BigDecimal(c);
 this.d = new BigDecimal(d);
 }
 Matrix multiply(Matrix m){
 return new Matrix(
 Matrix.segment(a,b,m.a,m.c),
 Matrix.segment(a,b,m.b,m.d),
 Matrix.segment(c,d,m.a,m.c),
 Matrix.segment(c,d,m.b,m.d));
 }
 Matrix square(){
 return multiply(this);
 }
 public Matrix remainder(String divisorString){
 BigDecimal divisor = new BigDecimal(divisorString);
 return new Matrix(a.remainder(divisor),
 b.remainder(divisor),
 c.remainder(divisor),
 d.remainder(divisor));
 }
 private static BigDecimal segment(BigDecimal q, BigDecimal r, BigDecimal s, BigDecimal t){
 return q.multiply(s).add(r.multiply(t));
 }
 @Override
 public String toString() {
 return "Matrix [a=" + a + ", b=" + b + ", c=" + c + ", d=" + d
 + "]";
 }
 static BigDecimal findNthFibonacciNumber(BigDecimal n){
 Matrix m = Matrix.ADVANCE[1];
 Matrix a = Matrix.IDENTITY;
 while (n.compareTo(BigDecimal.ZERO) > 0){
 if (n.remainder(new BigDecimal(2)).intValue() == 1){
 a = a.multiply(m).remainder("4294967291"); 
 }
 m = m.square().remainder("4294967291");
 n = n.divide(new BigDecimal(2), BigDecimal.ROUND_FLOOR);
 }
 // f(1) = 0, f(2)=1 일 때는 a.d를 출력.
 // f(0) = 0, f(1)=1 일 때는 a.b를 출력.
 return a.d;
 }
 static void findNthFibonacciNumber(int n){
 Matrix m = Matrix.ADVANCE[1];
 int nSave = n;
 Matrix a = Matrix.IDENTITY;
 while (n != 0){
 if (n%2 == 1){
 a = a.multiply(m).remainder("4294967291"); // 
 }
 m = m.square().remainder("4294967291");
 n/=2;
 }
 System.out.println("value = " + a.b);
 n = nSave;
 }
 }
 public static void main(String[] args){
 String[] inputs = new String[]{"5", "1000000000000000",
 "1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"
 };
 for (String input:inputs){
 System.out.println("input = " + input);
 System.out.println(Matrix.findNthFibonacciNumber(new BigDecimal(input)).toPlainString());
 System.out.println();
 }
 }
}

import java.math.BigInteger;
public class test {
 final static long DIVISOR = 4294967291L;
 static long fib(String S) {
 if (S == "1") {
 return 0L;
 }
 BigInteger N = new BigInteger(S);
 long t1 = 0L;
 long t2 = 1L;
 for (BigInteger i = new BigInteger("3"); i.compareTo(N) <= 0; i = i.add(BigInteger.ONE)) {
 long t3 = (t1 + t2) % DIVISOR;
 t1 = t2;
 t2 = t3;
 }
 return t2;
 }
 public static void main(String[] args) {
 System.out.println(fib("5"));
 System.out.println(fib("1000000000000000"));
 }
}

생각만큼 느리진 않은데.. 왜 답이 틀릴까요T.T

import java.util.Scanner;
import java.math.BigInteger;
public class Na{
 public static void main(String[] args){
 Scanner sc = new Scanner(System.in);
 BigInteger a = new BigInteger("0");
 BigInteger b = new BigInteger("1");
 BigInteger c = new BigInteger(a.add(b)+"");
 int i;
 long n = sc.nextLong();
 i = 2;
 while(i <= n){
 a = b;
 b = c;
 c = a.add(b);
 i++;
 }
 BigInteger d = new BigInteger("4294967291");
 BigInteger e = new BigInteger(c.remainder(d)+"");
 if(n == 1)
 System.out.println("1");
 else if(n == 2)
 System.out.println("2");
 else
 System.out.println(e);
 }
}

public static void main(String[] args) throws Exception {
 Scanner sc = new Scanner(System.in);
 long n = sc.nextInt(); 
 long f0 = 0;
 long f1 = 1;
 long f = 0;
 for (long i=0; i<n; i++) {
 if (n == 1) {
 f = 1; 
 break;
 }
 if (i == n-1) break;
 f = f1 + f0;
 f1 = f0;
 f0 = f;
 }
 System.out.println(f % 4294967291l);
 } // long으로 했는데도 음수 나오넹