本文主要是介绍soj2062 prison break,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
学会了快速求幂大法
不过怎么感觉也不是优势特别大,测试了下,比直接算好像不会快。。。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAX 100100
#define MOD 10000009
using namespace std;long long dg(long long m,long long n)
{if(n==0)return 1L;long long help;if(n%2==1L){help=dg(m,(n-1L)/2L);return ((((m%(long long)MOD)*(help%(long long)MOD))%(long long)MOD)*(help%(long long)MOD))%(long long)MOD;}else{help=dg(m,n/2L);return ((help%(long long)MOD)*(help%MOD))%MOD;}
}int main()
{long long n,m;while(scanf("%lld %lld",&n,&m)!=EOF)//)-(dg(m-1,n-1)*m)%MOD)%MOD{printf("%lld\n",(dg(m,n)+MOD-(dg(m-1,n-1)*m)%MOD)%MOD);}return 0;
}
这篇关于soj2062 prison break的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!