题目描述
小Biu所在的部落是一个魔法部落,部落中一共有n+1个人,小Biu是魔法部落中最菜的,所以他的魔力值为1,魔法部落中n个人的魔法值都不相同,第一个人的魔法值是小Biu的3倍,第二个人的魔法值是第一个人的3倍,以此类推。
现在小Biu想知道整个部落的魔法值和是多少?由于答案比较大,请把答案对1e9+7取模之后输出。
输入
输入一个数N(0 <= N <= 10^9)
输出
输出:整个部落的魔法值和模1e9+7。
样例输入
3
样例输出
40
提示
3^0+3^1+3^2+3^3 = 1+3+9+27 = 40
对于20%的数据,n<=100;
对于40%的数据,n<=1000000;
对于100%的数据,n<=1000000000;
取模后的结果之所以可以这样表示,就是因为x的值是3的n+1次方-1模去了偶数或者奇数个1e9+10才得到的结果。
#include<bits/stdc++.h> using namespace std; const int N = 1e9+7; typedef long long ll; ll k(ll a,ll b,ll y){ //快速幂取模 ll t = 1; while(b) { if(b%2 != 0) { t = (a*t)%y; b--; } a = (a*a)%y; b /= 2; } return t; } int main() { ll n; cin>>n; ll x = k(3,n+1,N); if((x-1)%2 != 0) { //判断奇偶 x = x + N; //如果是奇数就加上1e9+7让它变成偶数 } x = (x-1)/2; cout<<x<<endl; }
第二种写法就是逆元,这里只上板子,因为有很多的大佬已经写的很好了,所以具体的解析可以自己搜索
#include<bits/stdc++.h> using namespace std; const int N = 1e9+7; typedef long long ll; ll k(ll a,ll b,ll y) { ll t = 1; while(b) { if(b%2 != 0) { t = (a*t)%y; b--; } a = (a*a)%y; b /= 2; } return t; } long long quickpow(long long a, long long b) { if (b < 0) return 0; long long ret = 1; a %= N; while(b) { if (b & 1) ret = (ret * a) % N; b >>= 1; a = (a * a) % N; } return ret; } long long inv(long long a) { return quickpow(a, N - 2); } int main() { ll n; cin>>n; ll x = ((k(3,n+1,N)-1)%N*inv(2)%N)%N; cout<<x<<endl; }
原文链接: https://www.cnblogs.com/clb123/p/11743705.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/304872
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!