流离之人追逐幻影

用户名：pwj666

访问量：60209

签　名：

不想总是要失去后才懂得珍惜

等　　级
排　　名	37
经　　验	13957
参赛次数	11
文章发表	110
年　　龄	23
在职情况	在职
学　　校
专　　业

　　自我简介：

TA的其他文章

【原理、题解、代码】最大公约数与最小公倍数
浏览：186

你可能喜欢

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

快速幂与防爆 long long

　　作者: 流离之人追逐幻影　　　　发表时间：2019-10-19 15:31:46 浏览：676　|　评论：0　

![](/image_editor_upload/20191019022730_37690.png)

------------

思路
```
这道题一般会有两种做法，第一种是按照题目中给出的公式直接去做，不过有点消耗时间，第二种是通过打表从数字间找出规律，可以提炼出一个更好做的公式就是 res=n*(n+1)*2^(n-2)
```

ac代码（注意防爆long long ）
```
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MOD = 1000000007;
LL powMod(LL x, LL n)
{
	LL res = 1;
	x %= MOD;
	while (n>0)
	{
		if (n&1==1)
			res = (res*x) % MOD;
		x = (x*x)% MOD;
		n >>=1;
	}
	return res % MOD;
}
int main()
{
	int T;
	LL n,sum;
	scanf("%d",&T);
	while (T--)
	{
		scanf("%lld",&n);
		if (n == 1)
			printf("1\n");
		else{
			sum=((n%MOD+n%MOD*(n%MOD))*(powMod(2, n - 2)) % MOD) % MOD;
			printf("%lld\n",sum) ;
			//cout << (((n + powMod(n, 2)) % MOD)*(powMod(2, n - 2)) % MOD) % MOD << endl;
		}
    }
	return 0;
}
```
记录容易爆 long long 的地方
```
long long =[-2^63,2^63-1]
2^63=9,223,372,036,854,775,808‬;  10^19
n=[1,10^18]
MOD=1000000007

wa1:
sum=((n*(n+1))%MOD*powMod(2, n - 2) % MOD)%MOD;
因为n*(n+1)爆long long

wa2:
sum=((n%MOD*(n+1)%MOD)%MOD*powMod(2, n - 2) % MOD)%MOD;
因为n%MOD; n最大可达到MOD-1即10^9+6； 按照优先级计算的话，n%MOD*（n+1）爆long long 了；所以（n+1）%MOD要再加一层括号提高计算优先级;那么(10^9+6)*(10^9+6)<10^19，就可以ac了

wa3:
sum=((n+n*n)%MOD*powMod(2, n - 2) % MOD)%MOD;
n*n就已经爆了long long

wa4:
sum=((n%MOD+n%MOD*n%MOD)%MOD*powMod(2, n - 2) % MOD)%MOD;
同wa2的理由，注意计算优先级，n%MOD之后会直接与n相乘，爆long long 了
正确做法是sum=((n%MOD+n%MOD*(n%MOD))%MOD*powMod(2, n - 2) % MOD)%MOD;
```
快速幂运算
```
一般是 x^n%MOD  通常做法的时间复杂度为O(n)

快速幂做法：
res=1;
n是奇数 则 res=x*x^(n-1)// 2^5=2*2^4
n是偶数 则 res=x^(n-2)*x(n-2);//2^4=2^2+2^2
奇数都可化作偶数来计算
```

```
MOD ;
LL powMod(LL x, LL n)
{
	LL res = 1;
	x %= MOD;//降低数量级，防止下面运算爆long long
	while (n>0)
	{
		if (n&1==1)
			res = (res*x) % MOD;//res保存n为奇数时的每一个x之积
		x = (x*x)% MOD;//每次将幂x提升x倍
		n >>=1;//n%=2;,位运算更快一点
	}
	return res % MOD;
}
```

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

流离之人追逐幻影

TA的其他文章

你可能喜欢

C二级辅导-计负均正（C++代码）

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言训练-邮票组合问题* （C语言代码）

【计算两点间的距离】（C语言代码）

化学品问题（C语言代码）

快速幂与防爆 long long

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题12.2 （C语言代码）

C二级辅导-阶乘数列（C语言代码）

Wu-求圆的面积（C++代码）

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）

A+B for Input-Output Practice (VI) （C语言代码）

Tom数（C语言代码）

剪刀石头布（C语言代码）

勾股数（C语言代码）

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

三进制小数（C语言代码）

流离之人追逐幻影

TA的其他文章

你可能喜欢

C二级辅导-计负均正 （C++代码）

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言训练-邮票组合问题* （C语言代码）

【计算两点间的距离】 （C语言代码）

化学品问题 （C语言代码）

快速幂与防爆 long long

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题12.2 （C语言代码）

C二级辅导-阶乘数列 （C语言代码）

Wu-求圆的面积 （C++代码）

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）

A+B for Input-Output Practice (VI) （C语言代码）

Tom数 （C语言代码）

剪刀石头布 （C语言代码）

勾股数 （C语言代码）

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

三进制小数 （C语言代码）

C二级辅导-计负均正（C++代码）

【计算两点间的距离】（C语言代码）

化学品问题（C语言代码）

　　评论区

C二级辅导-阶乘数列（C语言代码）

Wu-求圆的面积（C++代码）

Tom数（C语言代码）

剪刀石头布（C语言代码）

勾股数（C语言代码）

三进制小数（C语言代码）