快速幂取模模板 && 51nod 1013 3的幂的和
2024-09-30 15:12:37
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
#include <string>
#include <set>
#include <functional>
#include <numeric>
#include <sstream>
#include <stack>
#include <map>
#include <queue>
#pragma comment(linker, "/STACK:102400000,102400000")
#define CL(arr, val) memset(arr, val, sizeof(arr)) #define ll long long
#define inf 0x7f7f7f7f
#define lc l,m,rt<<1
#define rc m + 1,r,rt<<1|1
#define pi acos(-1.0) #define L(x) (x) << 1
#define R(x) (x) << 1 | 1
#define MID(l, r) (l + r) >> 1
#define Min(x, y) (x) < (y) ? (x) : (y)
#define Max(x, y) (x) < (y) ? (y) : (x)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define E(x) (1 << (x))
#define iabs(x) (x) < 0 ? -(x) : (x)
#define OUT(x) printf("%I64d\n", x)
#define lowbit(x) (x)&(-x)
#define Read() freopen("a.txt", "r", stdin)
#define Write() freopen("b.txt", "w", stdout);
#define maxn 100010
#define mod 1000000007
using namespace std; ll quick_mod(ll a,ll b,ll c)
{
ll ans=;
while(b)
{
if(b&)
{
ans=(ans*a)%c;
b--;
}
b/=;
a=(a*a)%c;
}
return ans;
}
int main()
{
// freopen("a.txt","r",stdin);
ll a,b,c;
scanf("%lld%lld%lld",&a,&b,&c);
printf("%lld\n",quick_mod(a,b,c));
return ;
}
http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1013
这个题需要用到两次二分:第一次是在求3^n次方,第二次是求3^0+3^1+...3^n.
第一次二分就是上面的快速幂,第二次二分:
加入n=5 3^1+3^2+3^3+3^4+3^5 = 3^1+3^2 + 3^2*(3^1+3^2) +3^5
这样就可以递归求解了,跟矩阵快速幂类似。
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
#include <string>
#include <set>
#include <functional>
#include <numeric>
#include <sstream>
#include <stack>
#include <map>
#include <queue>
#pragma comment(linker, "/STACK:102400000,102400000")
#define CL(arr, val) memset(arr, val, sizeof(arr)) #define ll long long
#define inf 0x7f7f7f7f
#define lc l,m,rt<<1
#define rc m + 1,r,rt<<1|1
#define pi acos(-1.0) #define L(x) (x) << 1
#define R(x) (x) << 1 | 1
#define MID(l, r) (l + r) >> 1
#define Min(x, y) (x) < (y) ? (x) : (y)
#define Max(x, y) (x) < (y) ? (y) : (x)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define E(x) (1 << (x))
#define iabs(x) (x) < 0 ? -(x) : (x)
#define OUT(x) printf("%I64d\n", x)
#define lowbit(x) (x)&(-x)
#define Read() freopen("a.txt", "r", stdin)
#define Write() freopen("b.txt", "w", stdout);
#define maxn 100010
#define mod 1000000007
using namespace std; ll power(ll a,ll b)
{
ll ans=;
while(b)
{
if(b&)
{
ans=(ans*a)%mod;
b--;
}
b/=;
a=(a*a)%mod;
}
return ans;
}
ll c;
ll sum(ll a,ll k)
{
if(k == ) return a;
c=sum(a,k>>);
ll ans=(c+c*power(a,(k>>)))%mod; //每次 计算出两项
if(k&) ans=(ans+power(a,k))%mod; //是奇数的话要加上最后那一项
return ans;
}
int main()
{
//freopen("a.txt","r",stdin);
ll n;
scanf("%lld",&n);
//printf("%lld\n",(power(3,20)-1)/2%mod);
printf("%lld\n",((sum(,n)%mod))+);
return ;
}
最新文章
- ubuntu12.04samba服务器配置,亲测可用(转)
- 返璞归真vc++之感言
- JAVA TCP/IP Socket通信机制以及应用
- 一段C++代码想到的问题
- iOS音频处理
- [Protractor] Test Simple Binding With Protractor
- Javascript进阶篇——(DOM—节点---获取浏览器窗口可视区域大小+获取网页尺寸)—笔记整理
- 直插式精巧I/O模块:WIZ812MJ数据手册V1.1
- mysql 二级索引
- Canvas scale- 缩放
- jQ的一些常识
- fiddler 按条件过滤
- [转]Maven与nexus关系
- RABC --权限控制解读
- 可变数组(PLSQL)
- Shell - 简明Shell入门10 - 管道(Pipe)
- 机器翻译评价指标之BLEU详细计算过程
- 算法笔记_204:第四届蓝桥杯软件类决赛真题(Java语言C组)
- cf463d
- Top 5 SSH Clients for Windows (Alternatives of PuTTY)