rt,我的同学在校内OJ上(开O2)交了这样一份代码:
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define il inline
#define re register
const int mod=2148473647;
int n;
int Pow(int a,int b){
re int res=1;
while(b){
if(b&1)res=res*a%mod;
a=a*a%mod,b>>=1;
}
return res;
}
signed main(){
cin>>n;
cout<<n*(n+1)%mod*Pow((n<<2)-2,mod-2)%mod;
return 0;
}
并且AC了,其中 n≤109。但是在快速幂传参数时传入了 (n<<2)-2,这已经到达了 4×109 的量级,再平方就炸 long long 了,因此下面这组数据在本地是过不了的:
input:
998244353
output:
69361302
但是开了O2貌似就把它优化掉了,不开O2交在OJ上也过不了,想问一下这是怎么优化的,原理是什么,谢谢。