试题 算法训练 数的潜能

资源限制

内存限制：256.0MB   C/C++时间限制：1.0s   Java时间限制：3.0s   Python时间限制：5.0s

问题描述

　　将一个数N分为多个正整数之和，即N=a1+a2+a3+…+ak，定义M=a1*a2*a3*…*ak为N的潜能。
　　给定N，求它的潜能M。
　　由于M可能过大，只需求M对5218取模的余数。

输入格式

　　输入共一行，为一个正整数N。

输出格式

　　输出共一行，为N的潜能M对5218取模的余数。

样例输入

10

样例输出

36

数据规模和约定

　　1<=N<10^18

这是一道总结规律题，其实就是要看怎么组合才能使积最大，参考网友博客：http://t.csdnimg.cn/R75oA 

代码如下，不过要注意一下，直接算指数幂可能会超时，得优化指数幂的计算，将幂逐一分半来算，比如2的8次方分成两个2的4次方相乘，这样只需要计算一个2的4次方便可，这样就可以减少很多计算量。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll power(ll bottom,ll count){if(count==0)return 1;else if(count==1)return bottom;else if(count%2==0){ll temp=power(bottom,count/2);return temp%5218*temp%5218;}else{ll temp=power(bottom,count/2);return temp%5218*temp*bottom%5218;}
}
int main(){ll n;cin>>n;ll count3=0,count2=0;if(n<=3){cout<<n;return 0;}if(n%3==0)count3=n/3;else if(n%3==1){count3=n/3-1;count2=2;}else{count3=n/3;count2=1;}ll sum=power(3,count3);cout<<count3<<" "<<sum<<endl;sum*=pow(2,count2);cout<<sum%5218<<endl;}