首页 > 其他分享 >快速幂和大数取模的简单运用(以SPOJ LASTDIG - The last digit为例)

快速幂和大数取模的简单运用(以SPOJ LASTDIG - The last digit为例)

时间:2024-10-31 16:08:38浏览次数:1  
标签:取模 digit last power ll long base ans Nestor

题目描述

  • 原文

Nestor was doing the work of his math class about three days but he is tired of make operations a lot and he should deliver his task tomorrow. His math’s teacher gives him two numbers a and b. The problem consist of finding the last digit of the potency of base a and index b. Help Nestor with his problem. You are given two integer numbers: the base a (0 <= a <= 20) and the index b (0 <= b <= 2,147,483,000), a and b both are not 0. You have to find the last digit of \(a^{b}\) .

  • 中文翻译

Nestor 在数学课上做了三天的作业,但他已经厌倦了大量的运算,明天就该完成任务了。数学老师给了他两个数字 a 和 b。问题是找出基数 a 和指数 b 的结果的最后一位数。请帮助 Nestor 解决这个问题。老师给了你两个整数:基数 a(0 <= a <= 20)和指数 b(0 <= b <= 2,147,483,000),a 和 b 都不为 0。您必须找出 \(a^{b}\) 的最后一位数。

Input

The first line of input contains an integer t, the number of test cases (t <= 30). t test cases follow. For each test case will appear a and b separated by space.
第一行输入包含一个整数 t,即测试用例数(t <= 30)。每个测试用例的 a 和 b 用空格隔开。

Output

For each test case output an integer per line representing the result.
每个测试用例每行输出一个整数,代表测试结果。

Example

Input Output
2
3 10
6 2
9
6

题解

一道快速幂&取余运算的模板题(笑-)。

快速幂

快速幂是一种能迅速把\(a^{b}\) 求出来的算法,可以降低时间复杂度,防止TLE。

这里主要用了二分和递归的思路,把底数进行二分。当指数为偶数时,底数进行相乘,将指数除以2;当指数为奇数的时候,提出来一项底数,用ans进行积累,然后再按照偶数的方法递归。

long long qpow(long a,long n)
{
    long long ans = 1;
    while(n)
    {
        if (n % 2) ans *= a;//指数为奇数
        a = a * a;//底数平方
        n /= 2;//指数减半
    }
    return ans;
}

大数取模

  • 原理展示

#include <iostream>
typedef long long ll;
using namespace std;
#define endl '\n'
int main()
{
    ll base,power;
    cin >> base >> power;
    
        if (base == 0 && power == 0) break;
        ll res = 1;
        //执行power次循环,每次结果都乘一个base,即base的power次方
        for (ll i = 1;i <= power;i++)
        {
            res = res * base;
            res = res % 10;
        }
        ll ans = res % 10;
        cout << ans << endl;
    return 0;
}

AC代码

#include <iostream>
typedef long long ll; 
#define endl '\n'
using namespace std;
int t; ll a,b;ll c;
ll qpow(ll a,ll n)
{
    ll ans = 1;
    while(n)
    {
        if (n & 1) ans = ans * a % 10;//位运算
        a = a * a % 10;
        n >>= 1;//n >> 1可将原数减半,n >>= 1等价于n = n / 2
    }
    return ans;
}
void solve()
{
	cin>>a>>b;
	c=qpow(a,b);
	cout<<c<<endl;
}
int main()
{std::ios::sync_with_stdio(false);
     cin.tie(0);
     cout.tie(0);//降低时间复杂度
    cin>>t;
    while(t--)
    {
    	solve();
    }
    return 0;
}

标签:取模,digit,last,power,ll,long,base,ans,Nestor
From: https://www.cnblogs.com/ning0713/p/18518146

相关文章

  • Elasticsearch (ES) 的 ORM(对象关系映射)库
    Elasticsearch(ES)的ORM(对象关系映射)库有几个常用的选择,主要用于简化与Elasticsearch的交互。以下是一些比较流行的库及其特点:1.Elasticsearch-py这是Elasticsearch的官方Python客户端库,不是传统意义上的ORM,但它提供了与Elasticsearch进行交互的丰富API。你可以......
  • (ICCV2023)多尺度空间特征提取模块,有效涨点,即插即用
    题目:SAFMN:Spatially-AdaptiveFeatureModulationforEfficientImageSuper-Resolution期刊:CVPR(ConferenceonComputerVisionandPatternRecognition)GitHub地址:https://github.com/sunny2109/SAFMN年份:2023作者单位:TheChineseUniversityofHongKong(CUHK)......
  • Linux Docker 部署 Elasticsearch (ES) 集群详解教程
    1.安装Docker首先,确保你的Linux系统上已经安装了Docker。如果尚未安装,可以通过以下命令进行安装:sudoyuminstall-yyum-utilssudoyum-config-manager--add-repohttps://download.docker.com/linux/centos/docker-ce.reposudoyuminstalldocker-cedocker-ce......
  • ElasticSearch知识点小记
    ElasticSearch索引的基本操作#创建索引PUT/index_name可以初始不定义{ "settings":{ //索引设置 "number_of_shards":"1",//索引的分片书决定了索引的并行度和数据分布不可以动态修改 "number_of_replicas":"1",//副本的数量提高了数据的可用性和容错能力可以动态......
  • ElasticSearch - Bucket Script 使用指南
    文章目录官方文档BucketScript官文1.什么是ElasticSearch中的BucketScript?2.适用场景3.BucketScript的基本结构4.关键参数详解5.示例官方示例:计算每月T恤销售额占总销售额的比率百分比示例计算:点击率(CTR)6.注意事项与限制7.最佳实践官方文档ht......
  • 【项目实战】分布式日志搜索系统之数据同步方案(Logstash-input-jdbc、go-mysql-elast
    在构建分布式日志搜索系统时,数据同步是一个核心环节。以下是针对您提出的五种数据同步方案的详细分析:一、Logstash-input-jdbcLogstash是ElasticStack的一部分,用于从各种来源收集数据,并将其发送到Elasticsearch。Logstash-input-jdbc插件允许Logstash从关系型数据库(如My......
  • 【项目实战】分布式日志搜索系统之Elastic Stack日志抽取(filebeat、heartbeat、packet
    一、ElasticStack是什么?ElasticStack,以前称为ELKStack,是一套开源的日志分析解决方案。ElasticStack,由Elastic公司开发和维护。ElasticStack,包括了几个核心组件,这些组件协同工作以帮助用户收集、处理、存储、搜索和可视化数据。ElasticStack,因其灵活性和强大的功能......
  • Rust整合Elasticsearch
    Elasticsearch是什么Lucene:Java实现的搜索引擎类库易扩展高性能仅限Java开发不支持水平扩展Elasticsearch:基于Lucene开发的分布式搜索和分析引擎支持分布式、水平扩展提高RestfulAPI,可被任何语言调用ElasticStack是什么ELK(ElasticStack):Elasticsearch结合Kibana、Log......
  • elasticsearch使用
    1、选择1、ElasticsearchRestTemplate是spring对官方HighLevelRESTClient的封装。2、ElasticSearch8.x弃用了HighLevelRESTClient,移除了JavaTransportClient,推荐使用ElasticsearchJavaAPI(后续使用8的建议使用ElasticsearchJavaAPI)2、ElasticsearchRestTemp......
  • ElasticSearch安装与使用
    一、ElasticSearch的安装下载ElasticSearch安装包可以从ElasticSearch的官方网站下载相应版本的安装包。或者,在Linux系统中,可以使用wget命令下载,例如:wgethttps://artifacts.elastic.co/downloads/elasticsearch/elasticsearch-7.x.x-linux-x86_64.tar.gz(请将7.x.x替换为具......