蓝桥杯算法训练数的潜能

资源限制
时间限制：1.0s 内存限制：256.0MB问题描述
将一个数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 思路

(1) n = 1 , ans=1;(2) n > 1 , 假设 n = a1 + a2; 且 a1<=a2 1、a1=1 且 a2=1, 则 ans=1 2、设a1=1, a2>1, 则 设a2=c+d 若存在c,d 使 a2=c+d<=c*d, 说明a2可以再分, 此时有a2>=4 反之若对所有c,d 使 a2=c+d>c*d, 说明a2不可以再分, 此时只有a2=2,3 3、设1=4或a2>=4, 则 可以继续分解, 分解为一系列2和3的和当 2的个数大于3个时， 3个2可以转化为2个3, 而且也必须转化为两个3, 因为3*3>2*2*2即一系列数中至多只有两个2 综上所述：当n=[1 2 3]时, ans=[1 1 2] 当n>4时, n分解为至多2个2和一系列的3

易错点：pow(a, b)的返回值是double, 需要四舍五入转成int 即int(pow(a, b)+0.5) , 直接int()转可能会出错

#include#includeusing namespace std;long long int n;//正整数n int ans; //函数功能：快速幂取余 返回(a^b)%p //主要思想：设b=c0*2^0 + c1*2^1 + ..、+ ck*2^k ; //则a^b = a^(c0*(2^0)) * a^(c1*(2^1)) * ..、* a^(ck*(2^k)) //故a^b%p = ( (a^(c0*(2^0)))%p * (a^(c1*(2^1)))%p * ..、* (a^(ck*(2^k)) ) %p//且 (a^(2^k))%p = ((a^(2^(k-1))) %p)^2 %pint f(int a, long long int b, int p){int ans=1;int i=0;int temp=a%p; //temp = a^(c0*(2^0)) %pans = (ans * int(pow(temp, b&1)+0.5) ) %p; //ans = (a^(c0*(2^0)))%pb >>= 1;while(b>0){temp = (temp*temp) %p; ans = (ans * int(pow(temp, b&1)+0.5)) %p;b >>= 1;}return ans;} int main(){cin>>n;if(n<3){cout<