企业官网建设流程全解析

UVA324 Factorial Frequencies

Link: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=5&page=show_problem&problem=260

题目描述

PDF

输入格式

输出格式

输入输出样例 #1

Solution

1. 题意

• 输入多组数据；
• 每组数据输入整数n ( n < 366 ) n(n<366)n(n<366)，输出n ! n!n!中，数字0 ∼ 9 0\sim90∼9出现的频次。输入0 00表示结束。

2. 分析

典型的高精度问题，可以用 Java 的 BigInteger 解决。首先利用 BigInteger 计算出1 ∼ 366 1\sim3661∼366的阶乘的值，然后调用其 ToString 方法转化为字符串，统计每个数字字符出现的频次，记录在一个数组中。然后针对每次查询，用O ( 1 ) O(1)O(1)的复杂度完成查询输出即可。

唯一需要注意的是控制输出格式。

3. 代码

importjava.math.*;importjava.util.*;publicclassMain{staticint[][]cnt=newint[375][12];publicstaticvoidinit(){BigIntegerinitval=newBigInteger("1");for(inti=1;i<=370;i+=1){initval=initval.multiply(BigInteger.valueOf(i));Stringstr=initval.toString();for(intj=0;j<str.length();j+=1)cnt[i][str.charAt(j)-48]+=1;}}publicstaticvoidmain(String[]args){init();Scannercin=newScanner(System.in);while(true){intn=cin.nextInt();if(n==0)return;System.out.println(n+"! --");for(inti=0;i<=4;i+=1)System.out.print(" ("+i+")"+String.format("%5d",cnt[n][i]));System.out.println();for(inti=5;i<=9;i+=1)System.out.print(" ("+i+")"+String.format("%5d",cnt[n][i]));System.out.println();}}}