当前位置：首页 > news >正文

OJ 趣味程序设计＿高次方数

news 来源：原创 2024/5/18 17:33:23

趣味程序设计＿高次方数

时间限制: 1 Sec
内存限制: 128 MB

题目描述

求13的n次方（12<n≤130000000000）的最后三位数。例如：13的13次方的最后三位数是253，13的20次方的最后三位数是801。

输入

有多组测试数据

每组测试数据一行，即整数n。以文件结尾符结束。

输出

输出13的n次方的最后三位数。

样例输入

13
20

样例输出

253
801

提示

本题用64位数据类型也解决不了问题，因为13的n次方可能会非常大，所以要简化问题。不难发现，2个数乘积的后三位实际上只跟乘数的后三位有关，利用这一特点，可使问题大大简化。另外，n可达10的11次方，如果真的循环做n次乘法，肯定也会超时，所以，就要考虑减少乘法次数。考虑到连续乘的是"同一个数"，后三位数值变化一般具有周期性。那如何检测周期长度呢？如果第1次遇到后三位数为XYZ，在不断累乘的过程中，后三位数再次是XYZ时，即可界定一个周期。

解题思路

写出20行就可以找规律、

答案

#include <stdio.h>
#include <stdlib.h>
int a (int n);
int main()
{
    int n,i,c;
    while(scanf("%d",&n)!=EOF)
    {
        printf("%03d\n",a(n)%1000);
    }
    return 0;
}

int a (int n)
{
    return n == 1 ? 13 : ((a(n-1)%1000)*3+(a(n-1)%100)*10);
}

刚开始用递归时间超限了
在这里插入图片描述

#include <stdio.h>
#include <stdlib.h>

int main()
{
   long long int n;
   int i,sum=1;
    while(scanf("%lld",&n)!=EOF)
    {
        sum =1;
        if(!n%100)
        {
            printf("001\n");
            continue;
        }
        else
        {
            for(i=1; i<=n%100; i++)
            {
                sum = (sum%1000)*13;
            }
            printf("%03d\n",sum%1000);
        }
    }
    return 0;
}