7-7 快速幂运算 (10 分)

雨点打透心脏的1/2处 2023-10-11 16:24 12阅读 0赞

7-7 快速幂运算 (10 分)

编程求x^y最后三位数表示的整数

#### 输入格式: ####

输入在一行中给出两个整数x和y,其中1<=x,y<=1000000000

#### 输出格式: ####

输出占一行,是x^y的最后三位表示的整数。

#### 输入样例1: ####

在这里给出一组输入。例如：

2 3

#### 输出样例1: ####

在这里给出相应的输出。例如：

8

#### 输入样例2: ####

在这里给出一组输入。例如：

12  6

#### 输出样例2: ####

在这里给出相应的输出。例如：

984

**算法分析：**题目的要求我们要读懂，当我们计算的数字是三位以内（包含三位）的话，就输出当前的数字，当结果超过三位，我们就输出该数字的后三位。由y的数据范围我们可以看出，需要计算很大的数，所以我们一般的数据范围是无法存储的，而且一般的计算方法也是超时的，所以我们需要使用分治法，因为幂运算可以分成两个相等的数相乘获得，再结合递归可以实现。数据的溢出，我们需要利用取余的手段，我们每次都对递归出的结果进行1000取余，一直都对后三位进行运算。

**代码实现：**

#include<bits/stdc++.h>
    using namespace std;
     int quickpow(int a, int b){
    	if(b == 1)
    	{
    		return a;
    	}
    	else
    	{
    		int c = quickpow(a, b / 2);
    		if(b % 2 == 0)
    		{
    			int m=c*c%1000;
    			return m;
    		}
    		else
    		{
    			int n=c*c*a%1000;
    			return n;
    		}
    	}
    }
    
    int main(){
    	int a=0,b=0;
    	cin>>a>>b;
    	int m=quickpow(a,b);
    	int c[3];
    	for(int i=2;i>=0;i--)
    	{
    		c[i]=m%10;
    		m /=10;
    	}
    	int sum=0;
    	sum +=c[0]*10*10+c[1]*10+c[2];
    	cout<<sum;
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，12人围观）

还没有评论，来说两句吧...

相关阅读

相关 7-7 快速幂运算 (10 分)

7-7 快速幂运算 (10 分) 编程求x^y最后三位数表示的整数输入格式: 输入在一行中给出两个整数x和y,其中1<=x,y<=1000000000 输出格式

雨点打透心脏的1/2处/ 2023年10月11日 16:24/ 0 赞/ 13 阅读

相关幂运算

幂的概念：幂是乘方运算得结果，乘方运算涉及三个概念底数、指数和幂，如下图 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_s

谁借莪１个温暖的怀抱￠/ 2022年12月11日 02:22/ 0 赞/ 119 阅读

相关快速幂运算

include<iostream> using namespace std; typedef long long ll;

今天药忘吃喽~/ 2022年08月03日 14:52/ 0 赞/ 131 阅读

相关快速幂运算

/\ \ 基准时间限制：1 秒空间限制：131072 KB 分值: 0 难度：基础题收藏关注给出3个正整数A B C，求A^B Mod C。例如，3 5

朴灿烈づ我的快乐病毒、/ 2022年07月26日 06:31/ 0 赞/ 179 阅读

相关矩阵运算，矩阵快速幂，模板

include<cstdio> include<algorithm> include<cstring> include<iostream>

以你之姓@/ 2022年06月11日 05:41/ 0 赞/ 193 阅读

相关快速幂，矩阵快速幂（模板）

1，整数快速幂： C++ Code <table style="width:100%;font-family:Consolas, 'Courier New';font-

左手的ㄟ右手/ 2022年06月11日 03:57/ 0 赞/ 270 阅读

相关快速幂和矩阵快速幂

前言新年第一篇技术类的文章，应该算是算法方面的文章的。看标题：快速幂和矩阵快速幂，好像挺高大上。其实并不是很难，快速幂就是快速求一个数的幂（一个数的 n 次方）。

╰+攻爆jí腚メ/ 2022年06月01日 08:10/ 0 赞/ 263 阅读

相关矩阵快速幂+整数快速幂

嗯~ 今天总结一下快速幂的知识点 1.首先讲一下矩阵相乘矩阵A与矩阵B相乘的前提条件：A矩阵的列必须和矩阵B的行相等。若A矩阵是m\p的矩阵，那么B矩阵必定是p\n的

缺乏、安全感/ 2022年05月11日 13:22/ 0 赞/ 287 阅读

相关组合数学 (一): 快速幂运算

快速幂快速幂运算 C语言实现应用快速幂运算普通幂运算复杂度为 O(N) 快速幂运算复杂度为 O(lgN) 举个例子: 如

谁践踏了优雅/ 2022年03月21日 08:58/ 0 赞/ 254 阅读

相关幂运算

//1.基本实现方法递归时间复杂度O(n) double pow(int x,int n){ if(n<0)

短命女/ 2021年09月26日 13:06/ 0 赞/ 270 阅读