牛客网NC78-20.7.22-快速幂?
链接：牛客网NC78
题意：定义f(x) = xa+ x(a+1) +…+ x(b-1) + xb，然后在给定a和b的情况下，求f(x)%10000000033的值。
输入：第一行a,b,x, 其中0<=x,a,b<=1e9, 且 a<=b
输出：f(x)%10000000033的值
分析：首先想到等比数列公式，得
f(x)=(xb+1-xa)/(x-1)
但是不行，想想看，因为
ab%mod=(a%mod)(b%mod)
所以对于幂和乘法可以逐步取余，但除法？。。不会搞。
看了别人的说明，使用费马小定理（如果p是一个质数，而整数x不是p的倍数，即是：
【牛客网NC78-20.7.22-快速幂?】x(p-1)%p=1? ? \Rightarrow ??(x*x(p-2))%p=1
?????????? ? \Downarrow ?
???(x%mod) *(x(p-2)%p）=1,
x%mod和x(p-2)%p互为逆元，又因为mod=10000000033是质数，且x不可能是它的质数则
f(x)=(xb+1-xa)/(x-1)%mod
=(xb+1-xa) %mod * (1/(x-1))%mod
=(xb+1-xa) %mod * (x-1)(mod-2)%mod
这样就可以求f(x)了。
为了不超时，用快速幂，快速乘法。
思路：如分析，另外，0和1的时候要特判，1我知道是求（x-1)(mod-2)%mod的时候会得到零从而结果为0不符题意，0的话我不知道，按道理应该没问题，(xb+1-xa) %mod为0，(x-1)(mod-2)%mod随便得到一个数，结果依然为0，莫非是数据的问题？多希望有人给我说说为啥，wx GREAT-LIFE-21,难受.
代码：
import java.util.*;
public class Solution {
/**
*
* @param a int整型
* @param b int整型
* @param n int整型
* @return long长整型
*/
private static long Mod=10000000033L;
private static long qm(long a,long b){
long ans=0;
while(b!=0){
if(b%2==1){
ans=ans+a;
if(ans>=Mod)ans-=Mod;
}
a<<=1;
if(a>=Mod)a-=Mod;
b>>=1;
}
return ans;
}
private static long qq(long a,long b){
long ans=1;
while(b!=0){
if(b%2==1){
if(ans>=1;
}
return ans;
}
public long solve (int a, int b, int n) {
// write code here
if(n==0)return 0;
if(n==1)return b-a+1;
long ans=(qq(n,b+1)-qq(n,a)+Mod)%Mod;
long hh=qq(n-1,Mod-2);
return qm(ans,hh);
}
}
` 推荐阅读
- parallels|parallels desktop 解决网络初始化失败问题
- 猎杀IP
- 自媒体形势分析
- 数学大作战
- 使用协程爬取网页，计算网页数据大小
- 【亲测好用】高逼格配色网站推荐
- 2018.03.18
- 星期天的下午茶（一）
- 很多网红在用的素颜霜，你知道它是属于护肤品还是化妆品吗（）
- 08黑龙江迟淑荣弯柳树网络学院第五期学习赵宗瑞老师主讲的（传统文化与身心健康）教育体系心得体会