题解 | #牛牛的函数#
牛牛的函数
http://www.nowcoder.com/practice/9d90c461f30e46d29500fbc0d9a24634
描述
这是一篇面对初级coder的题解。
知识点：数学 快速幂 等比数列 费马小定理
难度：三星
题解
题目：
定义函数 ，然后在给定a和b的情况下，求f(x)%10000000033的值。
分析：
首先需要用等比数列的求和公式对
计算乘方可采用
中的快速幂算法
方法一：直接计算
之前的乘方算法化简到最简单依旧需要计算两个大数乘法
long long 是8字节 两个long long相乘就到了是16字节，同时由于由于取模运算的模太大，所以必须对乘法进行处理，否则乘法溢出！
类比竖式乘法：设计如下乘法逻辑，对每步乘法运算取模 保证乘法不溢出：
class Solution {
const long long mod=10000000033LL;//取余常数
public:
long long power(long long base, long long exponent) {
if(exponent==0)
return 1;
long long answer = 1;
while(exponent){
if(exponent&1) //如果n的当前末位为1
answer =multi(answer,base); //ans乘上当前的a
base =multi(base,base); //a自乘
exponent >>= 1; //n往右移一位
}
return answer;
}
long long multi(long long a, long long b) {//防止越界 乘法 每次只乘2字节
long long ans =0;
while(b){
ans=(ans+a*(b&0xFFFFLL))%mod;//相乘累加
b>>=16;//乘数右移2字节
a=(a<<16)%mod;//被乘数左移2字节
}
return ans;
}
long long solve(int a, int b, int n) {
if(n==0)
return 0; //处理特殊情况
long long ans=0;
for(int i=a;i<=b;i++){
ans+=power((long long)n,(long long)i) % mod;//按要求相加
ans =ans % mod;
}
return ans;
}
}; 复杂度分析：
时间复杂度：快幂法的时间复杂度都是)
，同时由于没有做优化，总共需要进行
次幂运算，所以时间复杂度为)
此处
空间复杂度 ，由于没有使用额外的空间 空间复杂度为 )
运行测试：
运行超时
运行时间1001ms 占用内存404KB
方法二：等比数列求和公式+费马小定理
考虑等比数列求和公式
但是其中的除法 
难以取模 所以这里需要用到费马小定理求逆元
在这样的基础上，推导
根据等比数列公式有
根据上面的费马小定理有
即：
代入上式得
程序中记：
则所求
class Solution {
const long long mod=10000000033LL;//取余常数
public:
long long power(long long base, long long exponent) {
if(exponent==0)
return 1;
long long answer = 1;
while(exponent){
if(exponent&1) //如果n的当前末位为1
answer =multi(answer,base); //ans乘上当前的a
base =multi(base,base); //a自乘
exponent >>= 1; //n往右移一位
}
return answer;
}
long long multi(long long a, long long b) {//防止越界 乘法 每次只乘2字节
long long ans =0;
while(b){
ans=(ans+a*(b&0xFFFFLL))%mod;//相乘累加
b>>=16;//乘数右移2字节
a=(a<<16)%mod;//被乘数左移2字节
}
return ans;
}
long long solve(int a, int b, int n) {
if(n==0)
return 0; //处理特殊情况
if(n == 1)//用费马小定理那步要求n！=1
return b - a + 1;//直接返回n=1值
long long a1=power((long long)n,(long long)a);
long long anq=power((long long)n,(long long)(b+1));
long long np=power((long long)n-1,(long long)(mod-2));
return multi(anq-a1+mod,np);
// write code here
}
}; 复杂度分析：
时间复杂度：快幂法的时间复杂度都是)
，同时由于采用费马小定理和等比数列求和公式做了优化，总共需要进行3次幂运算，
空间复杂度：由于没有使用额外的空间 空间复杂度为
运行测试：
运行时间： 3 ms 占用内存：400K
总结
数学知识很重要
阿Q的题解 文章被收录于专栏
阿Q秋招刷过的题
