지수의 마지막 숫자 - 오답 - C#

Question

이 문제를 해결하려고했습니다 : http://www.spoj.com/problems/LASTDIG/ 기본 및 지수를 취하고 지수 계산 결과의 마지막 숫자를 출력해야하지만 온라인 판사는 내 프로그램 일반적인 테스트 케이스에서는 잘못된 대답을하지만 내 산출물은 옳습니다.

NB : 나는 빠른 모듈러 지수화 알고리즘을 사용해야합니다, 여기에 대한 좋은 설명입니다 : https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/fast-modular-exponentiation

using System; 

public class Test 
{ 
    public static void Main() 
    { 
     int val = Convert.ToInt32(Console.ReadLine()); 
     for (int i=0; i<val; i++) 
     { 
      string input = Console.ReadLine(); 
      int a = Convert.ToInt32(input.Split()[0]); 
      int b = Convert.ToInt32(input.Split()[1]); 
      if (a==0) 
      { 
       Console.WriteLine(0); 
      } else if(b==0) 
      { 
       Console.WriteLine(1); 
      } else { 
       a=a%10; 
       string bToBinary=Convert.ToString(b, 2); 
       double temp = 1; 
       for(int j=bToBinary.Length-1, k=0; j>=0; j--, k++) 
       { 
        if (bToBinary[j] == '1') 
        { 
         temp = temp*(Math.Pow(a, Math.Pow(2, k))); 
        } 
       } 
       Console.WriteLine(temp%10); 
      } 
     } 
    } 
} 

샘플 입력 :

9 
6 
4 
1 

:이 프로그램에서

4 
3 10 
6 2 
14 11 
1 0 

출력

Answer 1

모든 전력이 반복하거나하여 중 1, 2 또는 여기

4.

를 기록 패턴

1 = {1,1,1,1} 
2 = {2,4,8,6} 
3 = {3,9,7,1} 
4 = {4,6,4,6} 
5 = {5,5,5,5} 
6 = {6,6,6,6} 
7 = {7,9,3,1} 
8 = {8,4,2,6} 
9 = {9,1,9,1} 

그리고 이미 같은 단위의 힘을위한 패턴을 알고 있습니다. (13)에 대한 패턴은 그래서 당신은

public class Test 
{ 
    public static void Main() 
    { 
     int val = Convert.ToInt32(Console.ReadLine()); 
     for (int i=0; i<val; i++) 
     { 
      string input = Console.ReadLine(); 
      int a = Convert.ToInt32(input.Split()[0]); 
      int b = Convert.ToInt32(input.Split()[1]); 
      if (a==0) 
      { 
       Console.WriteLine(0); 
      } else if(b==0) 
      { 
       Console.WriteLine(1); 
      } else { 
       Console.WriteLine (Math.Pow(a%10,b%4 + 4) %10); 
      } 
     } 
    } 
} 

Answer 2

당신은 용감한 해결책을 강요 당하지 않아야합니다. 문제 특히은 결과가 아닌 모든 결과가 인 마지막 숫자를 요청합니다.

남용 할 수있는 곱셈에는 어떤 종류의 패턴이 있어야합니다. 순간적으로 파워 0을 떨어 뜨리십시오. 왜냐하면 이것이 특정한 엣지 케이스이기 때문입니다. 예를 들어 양의 정수의 10 또는 20의 지수는 0으로 끝나고 5는 항상 5로 끝납니다.이 패턴을 악용 할 수 있습니다. 몇 번이나 우리가 힘을 올리더라도 마지막 숫자는 항상이 패턴 안에 있어야합니다.

IEnumerable<int> FindExpLastDigitPattern(int i) 
{ 
    var result = 1; 

    var list = new List<int>(); 
    while (!list.Contains(result = (result * i) % 10)) 
    { 
     list.Add(result); 
     yield return result; 
    } 
} 

그리고 또한 index = (power - 1) % pattern.Count되는 전력에 기초하여,이 패턴 내의 위치를 ​​예측할 수

패턴

같은 추출 될 수있다. 이를 염두에두고

, 우리는 지수의 마지막 자리 계산할 수

int ComputeLastDigitOfExponentiation(int i, int power) 
{ 
    // arguments guard... 

    // handles specific case 
    if (power == 0) return 1; 

    var pattern = FindExpLastDigitPattern(i).ToList(); 

    return pattern[(power - 1) % pattern.Count]; 
}