Problem Links:
USACO:Factorials,Problem:
PROGRAM NAME: fact4
INPUT FORMAT
A single positive integer N no larger than 4,220.SAMPLE INPUT (file fact4.in)
7
OUTPUT FORMAT
A single line containing but a single digit: the right most non-zero digit of N! .SAMPLE OUTPUT (file fact4.out)
4
Solution:
They only factor could result rear zeros is the product of 2 and 5,(10 could be handled as 2 * 5).So we count the number of 2s and 5s, obviously 2s are much more than 5s as you can see.
We keep multiply numbers, resulted by removing 2s and 5s, while counting the number of 2s and 5s.
At last, get the final result with 2s and 5s. Check out the code for details.
Source Code:
/* ID: *** TASK: fact4 LANG: JAVA */ import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.FileReader; import java.io.FileWriter; import java.io.PrintWriter; public class fact4 { public static void main(String[] args) throws Exception { fact4 main = new fact4(); main.run(); System.exit(0); } private void run() throws Exception { BufferedReader br = new BufferedReader(new FileReader("fact4.in")); PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter( "fact4.out"))); int N = Integer.parseInt(br.readLine()); br.close(); int cnt2 = 0; int cnt5 = 0; int prod = 1; for (int i = 1; i <= N; i++) { int tmp = i; while (tmp % 2 == 0) { tmp /= 2; cnt2++; } while (tmp % 5 == 0) { tmp /= 5; cnt5++; } prod = (prod * tmp) % 10; } if (cnt2 == cnt5) out.write(Integer.toString(prod)); else if (cnt2 > cnt5) { for (int i = 0; i < cnt2 - cnt5; i++) prod = (prod * 2) % 10; out.write(Integer.toString(prod)); } else { for (int i = 0; i < cnt5 - cnt2; i++) prod = (prod * 5) % 10; out.write(Integer.toString(prod)); } out.write("\n"); out.close(); } }
No comments :
Post a Comment