算法训练 数的潜能（python - c++）

资源

时间：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）元素不会超过4，因为4=2+2，又可以转化为2的问题，而5=2+3，5<2*3，所以5总能分解成2和3。
（2）尽可能多分解出3，然后分解出2，不要分出1。
考虑任意一个数，除以3之后的结果有以下3种：
（1）能被3除断，那么就分解为3+3+...+3的情况即可。例如9=3+3+3。
（2）被3除余1，分解为3+3+...+3+2+2或者3+3+...+3+4的情况，例如10=3+3+2+2
（3）被3除余2，分解为3+3+...+3+2的情况，例如11=3+3+3+2。

代码1：c++100%正确率，上面规律是分4，这里直接分8

#include<cstdlib>
#include<cstdio>
#include <iostream>
#include<cmath>
using namespace std;
int main()
{
    long long int n;
    scanf("%lld",&n);
    int R[10]={1,2,3,4,6,9,12,18,27,36};
    if (n <=10)
    {
        cout << R[n - 1];
        return 0;
    }
    long long int q, w, e=1;
    q = n / 9;
    w = n % 9;
    q%=2608;
    if(q==0) q=2608;
    if (w == 1)
    {
        for (long long int i = 0; i < q-1; i++)
        {
            e = e % 5218;
            e = e * 27;
        }
        e = (e * 36)%5218;
    }
    else if(w==0)
    {
        for (long long int i = 0; i < q; i++)
        {
            e = e % 5218;
            e = e * 27;        
        }
            e = e % 5218;
    }
    else
    {
        for (long long int i = 0; i < q; i++)
        {
            e = e % 5218;
            e = e * 27;     
        }
            e = (e * R[w - 1]) % 5218;
    }
    printf("%lld", e);
}

代码2:python直接使用规律，但是只有60%正确率

def mypow(k):
    res = 1
    for i in range(k):
        res = res*3
        res = res%5218
    return int(res)

n = int(input())
if n <= 4:
    result = n
if n%3 == 0 and n!=3:
    result = mypow(n//3)%5218
if n%3 == 1 and n!=1:
    result = 4*mypow((n//3)-1)%5218
if n%3 == 2 and n!=2 and n!=4:
    result = 2*mypow(n//3)%5218
print("%d"%result)