The factorial of an integer N, written N!, is the product of all the integers from 1 through N inclusive. The factorial quickly becomes very large: 13! is too large to store in a 32-bit integer on most computers, and 70! is too large for most floating-point variables. Your task is to find the rightmost non-zero digit of n!. For example, 5! = 1 * 2 * 3 * 4 * 5 = 120, so the rightmost non-zero digit of 5! is 2. Likewise, 7! = 1 * 2 * 3 * 4 * 5 * 6 * 7 = 5040, so the rightmost non-zero digit of 7! is 4.
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
题意:
给出一个数 N (1 ~ 4220),求出 N!,输出最右第一个非零的数。
思路:
数学。我的做法是直接保存后面的 K 位数,一旦有 0 就不断删除 0,最后输出 % 10 的答案即可。
官方解答是找出 2 和 5 的对数,因为 2 X 5 或者 5 X 2 是使末尾变为 0 的关键,所以找出 1 ~ N 中因子 2 的个数和因子 5 的个数,排除最大对数的 2 和 5 之后,剩下的数相乘就不会产生进位了,那么直接保存最后一位相乘的结果就好。因为 2 的个数肯定要比 5 的个数多,所以 5 的个数即为最大的对数,所以最后还要乘上剩下未匹配的 2,即乘上 (n5 - n2)个 2 后才是结果。
AC1:
/* TASK:fact4 LANG:C++ ID:sum-g1 */ #include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long ll; int main() { freopen("fact4.in", "r", stdin); freopen("fact4.out", "w", stdout); int n; scanf("%d", &n); ll last = 1; for (int i = 1; i <= n; ++i) { last *= i; while (!(last % 10)) last /= 10; last %= 100000000000; } printf("%lld\n", last % 10); return 0; }
AC2:
/* TASK:fact4 LANG:C++ ID:sum-g1 */ #include <cstdio> #include <cstring> #include <algorithm> using namespace std; int main() { freopen("fact4.in", "r", stdin); freopen("fact4.out", "w", stdout); int n; scanf("%d", &n); int n2 = 0, n5 = 0, last = 1; for (int i = 1; i <= n; ++i) { int j = i; while (!(j % 2)) { ++n2; j /= 2; } while (!(j % 5)) { ++n5; j /= 5; } last = (last * j) % 10; } for (int i = 1; i <= n2 - n5; ++i) last = (last * 2) % 10; printf("%d\n", last); return 0; }
相关推荐
C#,阶乘(Factorials)的递归、非递归、斯特林近似及高效算法与源代码 阶乘是基斯顿·卡曼(Christian Kramp,1760~1826)于 1808 年发明的运算符号,是数学术语。 一个正整数的阶乘(factorial)是所有小于及等于...
阶乘计算的 JavaScript 实现。 测试 $ npm test基准 $ npm run benchmark
用数学方法得出大集合有多少个排列 计算子集的排列 通过重复和替换计算排列 通过计数定义样本空间 让我们考虑以下示例。 下周,碧昂丝致敬乐队“ The Single Ladies”将在您当地的公园里播放免费的迷你演出。 他们...
用数学方法得出大集合有多少个排列 计算子集的排列 通过重复和替换计算排列 关于阶乘的注释 在上一课中,我们讨论了在覆盖范围内创建清单的情况下的排列。 我们想计算在订购清单中订购3首歌曲的方式。 我们可以为此...
目标你将能够: 用数学方法得出大集合有多少个排列计算子集的排列通过重复和替换计算排列关于阶乘的注释在上一课中,我们讨论了在覆盖范围内创建清单的情况下的排列。 我们想计算在订购清单中订购3首歌曲的方式。 ...
目标你将能够: 描述阶乘与排列的关系用数学方法得出大集合有多少个排列计算子集的排列通过重复和替换计算排列通过计数定义样本空间让我们考虑以下示例。 下周,碧昂丝致敬乐队“ The Single Ladies”将在您当地的...
析因查找器EpicodusJavaScript BDD实践,2015年9月14日夏季Brochtrup和Molly Waggett描述该网页允许用户输入数字以找出其阶乘。设置克隆此存储库。... 去!使用的技术JavaScript jQuery的摩卡咖啡hai合法的版权所有(c...
用数学方法得出大集合有多少个排列 计算子集的排列 通过重复和替换计算排列 关于阶乘的注释 在上一课中,我们讨论了在覆盖范围内创建清单的情况下的排列。 我们想计算在订购清单中订购3首歌曲的方式。 我们可以为此...
用数学方法得出大集合有多少个排列 计算子集的排列 通过重复和替换计算排列 关于阶乘的注释 在上一课中,我们讨论了在覆盖范围内创建清单的情况下的排列。 我们想计算在订购清单中订购3首歌曲的方式。 我们可以为此...
斐波那契/阶乘计算器 英语 我为Java编写的法语演示文稿编写了一个小应用程序,是在递归上完成的。 它按斐波纳契数列计算数字并递归分解,并在一个小巧,干净且美观的用户界面上显示它们。 该应用程序可以按以下...
Over1,100 common series, all grouped for easy reference.... binomials, simple inverse products, factorials, trigonometrical and hyperbolic expansions, and additional series. 1961 edition.
Sums containing descending factorials Summation formulas References Textbooks Papers Algorithms coded in Pascal and C Searching algorithms Sorting algorithms Selection algorithms Text ...
Sums containing descending factorials Summation formulas References Textbooks Papers Algorithms coded in Pascal and C Searching algorithms Sorting algorithms Selection algorithms Text ...
Pearls of discrete mathematics Pearls of discrete mathematicsPearls of discrete mathematicsPearls of discrete ...13 Divisibility of Factorials and Binomial Coefficients 97 14 Covering Systems 103
本文实例分析C语言的递归思想,分享给大家供大家参考之用。具体方法如下: 通俗点来说,递归就是自己... printf(This program calculates factorials.\n); printf(Enter a value in the range 0-12 (q to quit):\n);
现实鼠标 ... ##Basics 在这个项目中,我基本上是通过 Factorials、Bernstein 基础、Bezier Curves、Gaussian Distribution 实现的。 ##Update 当前错误:在某些情况下电弧过大。 (很快修复TM )
要使用其他字节码,您可以覆盖默认share/basic_test.bc与python share/basic_bytecode_generator.py您更改后N_factorials到你想要的值。 依赖关系 当您拥有现代系统时,以下依赖项很可能已经得到满足。 在 Ubuntu ...
} } 习题三 8、 public class Factorials { public static void main(String args[]) { int i, j; long s=0, k; i=1; do //外循环开始 { k = 1; j=1; do{//内循环开始 k = k * j; //内循环体 j++; }while(j);//内...
Python Cookbook英文版 Table of Contents Foreword Preface 1. Python Shortcuts 1.1 Swapping Values Without Using a Temporary Variable 1.2 Constructing a Dictionary Without Excessive Quoting ...