首页 > 其他分享 >A hard puzzle

A hard puzzle

时间:2023-05-05 20:32:58浏览次数:32  
标签:10 27 a% puzzle hard 38 复杂度


A hard puzzle


Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 30832 Accepted Submission(s): 11063



Problem Description


lcy gives a hard puzzle to feng5166,lwg,JGShining and Ignatius: gave a and b,how to know the a^b.everybody objects to this BT problem,so lcy makes the problem easier than begin.
this puzzle describes that: gave a and b,how to know the a^b's the last digit number.But everybody is too lazy to slove this problem,so they remit to you who is wise.





Input


There are mutiple test cases. Each test cases consists of two numbers a and b(0<a,b<=2^30)





Output


For each test case, you should output the a^b's last digit number.





Sample Input


7 66 8 800





Sample Output


9 6





解决方案:

假设a=38,b=2,那么结果应为(a*a)%10=(38*38)%10=[(38%10)*(38%10)]%10=4;

假设a=27,b=2,那么结果应为(a*a)%10=(27*27)%10=[(27%10)*(27%10)]%10=9;

.......

可以看出,(a^b)%10=(a*a*a......*a)%10=[(a%10)*(a%10)*(a%10)*.....(a%10)]%10;

那么就可以使用(b-1)次循环,求出(a^b)%10的结果,但这样时间复杂度就是O(b-1),提交给OJ后,会提出超时的警告。

所以需要一个时间复杂度更低的程序。

正整数a不管多大,都是十进制数,所以a%10的结果必然是0-9中的一个数。

0^n=0,那么只要以0结尾的数,该数的n次方的个位数还是0。

1^n=1,那么只要以1结尾的数,该数的n次方的个位数还是1。

同样以5结尾的数也是如此。那其它的数字又不一样,最后得出下列这张表:

A hard puzzle_Java

从红色的框中可以看出:0-9中任何一个数字,其n次方后的个位数是有规律的。每4次一个循环。所以只要先前列一个数组,将其

保存,就可以直接找到对应的数组元素就是其(a^b%10)的值,这样时间复杂度为0(1);

#include<iostream>
using namespace std;
int main()
{
    int a,b,col,row;
    int result[4][10]=
    {
        {0,1,6,1,6,5,6,1,6,1},
        {0,1,2,3,4,5,6,7,8,9},
        {0,1,4,9,6,5,6,9,4,1},
        {0,1,8,7,4,5,6,3,2,9}
    };
    while(cin>>a>>b)
    {
        row=b%4;//对周期4取余,其余数为0,1,2,3 
        col=a%10;


        cout<<result[row][col]<<endl;
    }
    return 0;
}

标签:10,27,a%,puzzle,hard,38,复杂度
From: https://blog.51cto.com/u_16099425/6247724

相关文章

  • Sharding-JDBC:实现数据库的读写分离?
    简介轻量级Java框架,在Java的JDBC层提供额外服务,以jar包的形式提供服务(增强版数据库连接驱动)。适用于基于JDBC的ORM框架、支持第三方数据库连接池、支持实现了JDBC规范的数据库。 读写分离:基于已配置好主从复制的多个数据库。 使用步骤在springboot项目中使用。一、......
  • [极客大挑战 2019]HardSQL,wp
    一:分析既然说了是HardSQL,肯定就不是万能密码这种简单的了1.首先判断字符型还是数字型我们首先输入payload:username=admin'--+&password=1发现好像有什么被过滤掉了。然后检查过滤符号,这里可以直接用bp爆破看看过滤了哪些字符,也可以简单测试一下这里我猜测过滤了空格, 然......
  • 终于有人把openGauss3.0.0分布式原理讲透了,openGauss X ShardingSphere分布式原理和部
    本文为原理精讲,部署文章链接如下https://www.cnblogs.com/opengauss/p/17364285.html一、opengauss的背景和行业现状2022年,七大openGauss商业版发布,是基于openGauss3.0推出商业发行版目前海量数据库Vastbase表现最佳,一直是TOP1作者认为之所以海量数据库Vastbase......
  • 终于有人把openGauss3.0.0分布式原理讲透了,openGauss X ShardingSphere分布式原理和部
    本文为原理精讲,部署文章链接如下https://blog.51cto.com/u_13808894/6236819一、opengauss的背景和行业现状2022年,七大openGauss商业版发布,是基于openGauss3.0推出商业发行版目前海量数据库Vastbase表现最佳,一直是TOP1作者认为之所以海量数据库Vastbase目前无法被同......
  • 解决Matlab在Linux下无法使用hardware OpenGL的问题
    解决Matlab在Linux下无法使用hardwareOpenGL的问题1报错信息在命令行使用命令matlab-nodesktop-nosplash启动Matlab时,出现如下报错:MATLABisselectingSOFTWAREOPENGLrendering.在查阅ArchWikiMatlabOpenGLAcceleration栏目后,发现这是因为Matlab未启用OpenGL硬件加......
  • 使用 Sharding Jdbc 实现读写分离
    上一篇博客介绍了MySQL的主从复制的搭建,为实现读写分离创造了条件。对于一个网站来说,80%来源于读操作,绝大多数情况下的网站宕机,都是由于过多的读操作导致的,因此在实际的生产环境中,经常会搭建一主多从的架构,主库只负责写操作,多个从库用来负责读操作,对于少量需要实时获取信息的读......
  • G2 - Magic Triples (Hard Version)
    题解:值域分治,降低时间复杂度到n*1000+map代码1:点击查看代码#include<bits/stdc++.h>usingnamespacestd;typedeflonglongLL;typedefpair<int,int>PLL;#defineIOScin.tie(nullptr)->sync_with_stdio(false);#definesesecond#definefifirst#definemem(a,b)......
  • 新建hardhat项目
    //初始化项目,一直回车即可yarninit//新增包之类的yarnadd--devhardhat//一直回车就行,初始化yarnhardhat//如果hardhat.config.js文件不在当前文件夹下yarnhardhat--verbose//该命令会帮助你找到错误的文件,然后删除他然后再次执行yarnhardhat编译命令yarnhardhat......
  • 解决Python中报错RequestsDependencyWarning: urllib3 (1.26.9) or chardet (5.1.0)/c
      在运行requests包时,出现了以下报错信息:RequestsDependencyWarning:urllib3(1.26.9)orchardet(5.1.0)/charset_normalizer(2.0.12)doesn'tmatchasupportedversion!warnings.warn("urllib3({})orchardet({})/charset_normalizer({})doesn'tmatchasu......
  • LightOJ1007---Mathematically Hard (欧拉函数)
    Mathematicallysomeproblemslookhard.Butwiththehelpofthecomputer,someproblemscanbeeasilysolvable.Inthisproblem,youwillbegiventwointegersaandb.Youhavetofindthesummationofthescoresofthenumbersfromatob(inclusive).T......