【数论系列】 指数与对数（数值优化）

大家好，欢迎来到IT知识分享网。

目录

一. 对数

1. 基本公式

2. 基本性质

3. 应用场景

4. 例题分析

一. 对数

1. 基本公式

（1）log（n）：以e为底的对数

（2）log10（n）：以10为底的对数

（3）换底公式：logx（n）= log（n）/log（x）

2. 基本性质

（1）负数与0无对数可言

（2）log(1) = 0；loga（a） = 1

（3）log（M*N） = log（M） + log（N）

（4）log（M/N） = log（M） – log（N）

（5）

（6）log（a^b） = b*log(a)

（7）若  ：则 m = logb（a）

（8）完全展开式

3. 应用场景

（1）用对数来进行数值优化，主要是把大数化为小树运算或者比较

（2）与对数/指数有关的题目

（3）与唯一分解定理联系：n = a^p1*b^p2*c^p3*……，则log(n) = p1log(a) + p2log(b) + p3log(c) + ……

4. 例题分析

（1）UVA 10883  Supermean

Problem Description

给你n个数字，让你求相邻数字的平均数n-1个，再求这n-1个平均数的平均数。。。求出最后一个数字（n<=50000）

        二项式系数+数值优化。很容易看出来 ，而double的范围为-2^1024 ~ +2^1024 ， 但这里达到了2^50000绝对超出double范围了，可以看出最后的结果却很小，也就是说我们必须把中间运算过程变小，这里就考虑对数的优化。

        直接取log10（sum） = log10（N[0]*C(n-1,0) + N[1]*C(n-1,1) + …..） – log10(2)*(n-1)中累和部分不能拆分，所以这里我们干脆一项一项的拆分即 sum += pow（10，log10(N[i]) + log10(C(n-1,i)) – log10(2)*(n-1)）；注意这里有负数，而负数没有对数，所以需要在负数时使用sum-= ， 在正数时使用sum+=；

        还要处理一下 C(n-1,i) ：C(n-1,i) = (n-i)/i*C(n-1,i-1)，log10( C(n-1,i)) = log10(n-i) + log10(C(n-1,i-1)) – log10(i)；

#include <iostream> #include<bits/stdc++.h> using namespace std; #define eps 0.000001 int main() { int T; int t = 0; //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); scanf("%d",&T); while(T--){ int n; scanf("%d",&n); t++; double sum = 0; double C = 0; for(int i = 0;i<n;i++){ double num; scanf("%lf",&num); if(i!=0)C = log10(n-i) + C - log10(i); if(num==0)sum+=0; else if(num < 0){ sum-=pow(10,log10(-num) + C - log10(2)*(n-1)); } else{ //cout<<num<<" "<<C<<" "<<n-1<<" "<<pow(10,log(10.4))<<endl; sum+=pow(10,log10(num) + C - log10(2)*(n-1)); } } printf("Case #%d: %.3lf\n",t,sum); } return 0; }