当前位置:网站首页>Informatics Orsay Ibn YBT 1172: find the factorial of n within 10000 | 1.6 14: find the factorial of n within 10000
Informatics Orsay Ibn YBT 1172: find the factorial of n within 10000 | 1.6 14: find the factorial of n within 10000
2022-07-07 01:02:00 【Jun Yi_ noip】
【 Topic link 】
ybt 1172: seek 10000 within n The factorial
OpenJudge NOI 1.6 14: seek 10000 within n The factorial
【 Topic test site 】
1. High precision
Investigate : High precision multiplication and low precision
Explanation of high-precision calculation
【 Their thinking 】
First find the largest digit of the result , That is to say 10000 ! 10000! 10000! Number of digits .
A positive integer is known x The number of digits of is n, So there are : n = ⌊ l g x ⌋ + 1 n = \lfloor lgx \rfloor + 1 n=⌊lgx⌋+1( l g x lgx lgx: With 10 Bottom x The logarithmic )
Bits are ⌊ l g 10000 ! ⌋ + 1 ≤ ⌊ l g 1000 0 10000 ⌋ + 1 = ⌊ 10000 ⋅ l g 10000 ⌋ + 1 = ⌊ 10000 ∗ 4 ⌋ + 1 = 40001 \lfloor lg10000! \rfloor + 1\le \lfloor lg10000^{10000} \rfloor + 1=\lfloor 10000\cdot lg10000 \rfloor + 1=\lfloor 10000*4 \rfloor + 1 = 40001 ⌊lg10000!⌋+1≤⌊lg1000010000⌋+1=⌊10000⋅lg10000⌋+1=⌊10000∗4⌋+1=40001
The length of the number array is 40005 that will do .
Because of the demand for 10000 The factorial , The number multiplied each time is less than or equal to 10000 The number of , Is a low precision number . The result of factorial is a high-precision number . So we should use high precision times low precision . If you use high precision times high precision , The complexity of the algorithm will increase , It may time out .
【 Solution code 】
solution 1: Use functions and arrays
#include <bits/stdc++.h>
using namespace std;
#define N 40005
void setLen(int a[], int i)
{
while(a[i] == 0 && i > 1)// Remove the superfluous 0
i--;
a[0] = i;
}
void Multiply(int a[], int b)//a *= b High precision multiplication and low precision
{
int c = 0, i;
for(i = 1; i <= a[0]; ++i)
{
a[i] = a[i]*b + c;
c = a[i] / 10;
a[i] %= 10;
}
while(c > 0)
{
a[i] = c % 10;
c /= 10;
i++;
}
setLen(a, i);
}
void toNum(char s[], int a[])
{
a[0] = strlen(s);
for(int i = 1; i <= a[0]; ++i)
a[i] = s[a[0] - i] - '0';
}
void showNum(int a[])
{
for(int i = a[0];i >= 1;--i)
cout << a[i];
}
int main()
{
int a[N] = {
1, 1}, n;// High precision number a The initial value is 1
cin >> n;
for(int i = 1; i <= n; ++i)
Multiply(a, i);
showNum(a);
return 0;
}
solution 2: Overloaded operator in class
#include <bits/stdc++.h>
using namespace std;
#define N 40005
struct HPN
{
int a[N];// Array of numbers
HPN()
{
memset(a, 0, sizeof(a));
}
HPN(char s[])
{
memset(a, 0, sizeof(a));
int len = strlen(s);
for(int i = 0; i < len; ++i)
a[len - i] = s[i] - '0';
a[0] = len;
}
void setLen(int i)
{
while(a[i] == 0 && i > 1)// Remove the superfluous 0
i--;
a[0] = i;
}
void operator *= (int b)//a *= b High precision multiplication and low precision
{
int c = 0, i;
for(i = 1; i <= a[0]; ++i)
{
a[i] = a[i]*b + c;
c = a[i] / 10;
a[i] %= 10;
}
while(c > 0)
{
a[i] = c % 10;
c /= 10;
i++;
}
setLen(i);
}
void show()
{
for(int i = a[0]; i >= 1; --i)
cout << a[i];
}
};
int main()
{
HPN a("1");// High precision digital a The initial value is 1
int n;
cin >> n;
for(int i = 1; i <= n; ++i)
a *= i;// High precision multiplication and low precision
a.show();
return 0;
}
边栏推荐
- Advanced learning of MySQL -- Fundamentals -- concurrency of transactions
- Learning notes 5: ram and ROM
- Advanced learning of MySQL -- Fundamentals -- four characteristics of transactions
- build. How to configure the dependent version number in the gradle file
- Advanced learning of MySQL -- basics -- multi table query -- subquery
- Dell笔记本周期性闪屏故障
- Zynq transplant ucosiii
- [C language] dynamic address book
- Summary of being a microservice R & D Engineer in the past year
- 随时随地查看远程试验数据与记录——IPEhub2与IPEmotion APP
猜你喜欢
随时随地查看远程试验数据与记录——IPEhub2与IPEmotion APP
批量获取中国所有行政区域经边界纬度坐标(到县区级别)
集合(泛型 & List & Set & 自定义排序)
用tkinter做一个简单图形界面
New feature of Oracle 19C: automatic DML redirection of ADG, enhanced read-write separation -- ADG_ REDIRECT_ DML
JS+SVG爱心扩散动画js特效
Batch obtain the latitude coordinates of all administrative regions in China (to the county level)
第六篇,STM32脉冲宽度调制(PWM)编程
pyflink的安装和测试
Js+svg love diffusion animation JS special effects
随机推荐
Explain in detail the matrix normalization function normalize() of OpenCV [norm or value range of the scoped matrix (normalization)], and attach norm_ Example code in the case of minmax
Advanced learning of MySQL -- basics -- multi table query -- external connection
动态规划思想《从入门到放弃》
Maidong Internet won the bid of Beijing life insurance to boost customers' brand value
Deeply explore the compilation and pile insertion technology (IV. ASM exploration)
【批處理DOS-CMD命令-匯總和小結】-字符串搜索、查找、篩選命令(find、findstr),Find和findstr的區別和辨析
深度学习之线性代数
Trace tool for MySQL further implementation plan
C9高校,博士生一作发Nature!
Meet the level 3 requirements of ISO 2.0 with the level B construction standard of computer room | hybrid cloud infrastructure
threejs图片变形放大全屏动画js特效
线段树(SegmentTree)
ZABBIX 5.0: automatically monitor Alibaba cloud RDS through LLD
用tkinter做一个简单图形界面
什么是时间
fastDFS数据迁移操作记录
Threejs image deformation enlarge full screen animation JS special effect
Dell笔记本周期性闪屏故障
Stm32f407 ------- DAC digital to analog conversion
Batch obtain the latitude coordinates of all administrative regions in China (to the county level)