LightOJ 1282 - Leading and Trailing (求n^k的前三位和后三位)_description given two integers nn n and kk k, find-程序员宅基地

技术标签: 数论  

1282 - Leading and Trailing
Time Limit: 2 second(s) Memory Limit: 32 MB

You are given two integers: n and k, your taskis to find the most significant three digits, and least significant threedigits of nk.

Input

Input starts with an integer T (≤ 1000),denoting the number of test cases.

Each case starts with a line containing two integers: n (2≤ n < 231) and k (1 ≤ k ≤ 107).

Output

For each case, print the case number and the three leadingdigits (most significant) and three trailing digits (least significant). Youcan assume that the input is given such that nk contains atleast six digits.

Sample Input

Output for Sample Input

5

123456 1

123456 2

2 31

2 32

29 8751919

Case 1: 123 456

Case 2: 152 936

Case 3: 214 648

Case 4: 429 296

Case 5: 665 669

 



思路:后三位很好求,快速幂取模就好了,同样前三位我们也可以模拟快速幂来写,用double存储答案,模拟一下快速幂,中间记得转换就好了,注意输出为3位,如果后三位是022,那么必须输出022,不能输出22




ac代码:

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<stack>
#include<set>
#include<queue>
#include<vector>
#include<iostream>
#include<algorithm>
#define MAXN 101000
#define LL long long
#define ll __int64
#define INF 0xfffffff
#define mem(x) memset(x,0,sizeof(x))
#define PI acos(-1)
#define eps 1e-8
using namespace std;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
ll powmod(ll a,ll b,ll MOD){ll ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
double dpow(double a,ll b){double ans=1.0;while(b){if(b%2)ans=ans*a;a=a*a;b/=2;}return ans;}
//head
double change(double x)
{
    while(x>=1000.0)
    {
        x/=10.0;
    }
    return x;
}
int main()
{
    int t,i;
    int cas=0;
    scanf("%d",&t);
    while(t--)
    {
        ll n,k;
        scanf("%I64d%I64d",&n,&k);
        int ans2=(int)powmod(n,k,1000);
        double ans1=1.0,a=n*1.0;
        while(k)
        {
            if(k%2)
            {
                ans1=ans1*a;
                ans1=change(ans1);
            }
            a=a*a;
            a=change(a);
            k/=2;
        }
        printf("Case %d: %d %03d\n",++cas,(int)ans1,ans2);
    }
    return 0;
}


版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/helloiamclh/article/details/51057792

智能推荐

普通二本院校计算机专业大学心得_普通二本能学计算机吗-程序员宅基地

文章浏览阅读5.2k次,点赞24次,收藏26次。前言​ 2019年9月2日,步入大四的第一天,这第一天有分感慨,却又不知道如何表达。马上就要步入社会了,身处普通二本院校(“吕梁学院”)计算机专业的我却对于前途未来并不担心,我这几年的努力,我自己知道。我这个人比较…比较执着,对!执着,更加形象。我想要的,都会通过自己的努力得到。而我现在想的,是想给学校留下点什么,想给下一个像我这样的人留下点什么。步入大学的迷茫​ 刚步入大学,没有..._普通二本能学计算机吗

三款性能测试工具kylinPET、LoadRunner、Jmeter在脚本录制与调试上的差异性_类似于loadrunner脚本录制软件-程序员宅基地

文章浏览阅读1w次,点赞6次,收藏52次。软件的性能测试活动离不开性能测试工具的支持。国外常用的性能测试工具有:loadRunner(商用),Jmeter(开源),国内做的比较好的国产性能工具有kylinPET。性能测试工具的录制和调试是能力的高低,是判断性能测试工具优劣重要指标。下面笔者通过实例来分析一下这三款知名本和调试上的差异点。测试工具选:Jmeter..._类似于loadrunner脚本录制软件

学习笔记(2):零基础掌握 Python 入门到实战-一个圆点的何去何从(二)-程序员宅基地

文章浏览阅读33次。【为什么学Python】 Python 是当今非常热门的语言之一,2020年的 TIOBE 编程语言排行榜中 ,Python名列第一,并且其流行度依然处在上升势头。 在2015年的时候,在网上还经常看到学Python还是学R的讨论,那时候老齐就选择了Python,并...

java去除HTML标签_java html去掉class标签-程序员宅基地

文章浏览阅读1k次。java去除HTML标签,去除class=MsoNormal/** * 去除html代码中含有的标签 * @param htmlStr * @return */ public static String delHtmlTags(String htmlStr) { //定义script的正则表达式,去除js可以防止注入 String scriptRegex="<script[^>]*?>[\\s\\S]*?&l_java html去掉class标签

机器学习(七)-- K-means聚类算法 ( k均值聚类算法)_k个初始化的质心位置选择对最后的聚类结果和运行时间均有很大的影响,因此需要选择-程序员宅基地

文章浏览阅读1.6k次。一、K-means聚类算法算法思想k-means算法实际上就是通过计算不同样本间的距离来判断他们的相近关系的,相近的就会放到同一个类别中去。1.首先我们需要选择一个k值,也就是我们希望把数据分成多少类,这里k值的选择对结果的影响很大,选择方法有两种一种就是根据聚类的结果和k的函数关系判断k为多少的时候效果最好。另一种则是根据具体的需求确定,比如说进行衬衫尺寸的聚类你可能就会考虑分成三类..._k个初始化的质心位置选择对最后的聚类结果和运行时间均有很大的影响,因此需要选择

人生还需要正能量_气我去者昨日之日不可留乱我心者今日之日多烦忧什么意思-程序员宅基地

文章浏览阅读492次。弃我去者,昨日之日不可留;乱我心者,今日之日多烦忧。无论是时光,还是往事,或是容颜,都如昨日之日一般弃我而去,任我多么留恋,它们却毫无回头之意。而今日之日又有诸多烦忧纷纷扰扰,挥之不去。人生就是有这样的错觉:逝去的总是美好的,拥有的总是缺憾的,于是,在眺望昨日的背影时,眼里只有烦恼的身影来来回回。_气我去者昨日之日不可留乱我心者今日之日多烦忧什么意思

随便推点

Cruise Control_cruise control安装和使用-程序员宅基地

文章浏览阅读1.8k次。Cruise Control 使用报告1. Cruise Control 介绍Cruise Control 是一种持续集成过程的框架,包括了邮件通知,ant 和各种源码控制工具的插件,并提供了 web 接口,用于查看当前和以前的创建的结果。 2. 下载安装在http://sourceforge.net/projects/cruisecontrol/fil_cruise control安装和使用

excel如何打开100万行以上的csv文件_csv跳转2560000行-程序员宅基地

文章浏览阅读4.2w次,点赞28次,收藏131次。前言正常情况下,2007版本以上的excel打开的csv文件,最多只能显示1048576行数据,如果我们恰好有一个超大csv文件行数超过这个量级,该如何解决呢,可以使用power query来解决。步骤1.切换到数据选项卡,依次点击 新建查询->从文件->从CSV,然后选择需要导入的超大csv文件2.在出现的窗口里,点击 加载 -> 加载到3.选择仅创建连接和将此数据添加到数据模型,点击加载4.等excel加载完数据后,在窗口的右侧会出现一个工作簿查询,点击里面的文件,_csv跳转2560000行

关于非全日制找实习_非全研究生在别的公司实习-程序员宅基地

文章浏览阅读1.6k次。https://www.zhihu.com/question/68031329?sort=created_非全研究生在别的公司实习

MTK 平台使用mtklogger 抓取日志-程序员宅基地

文章浏览阅读4.2k次。使用mtk工具 抓取系统日志_mtklogger

lInux安装jdk的三种方法_linux 安装jdk-13.0.1-程序员宅基地

文章浏览阅读271次。环境Linux版本:CentOS 6.5、Ubuntu 12.04.5JDK版本:JDK 1.7方法一:手动解压JDK的压缩包,然后设置环境变量方法二:用yum安装JDK方法三:用rpm安装JDK方法四:Ubuntu 上使用apt-get安装JDK方法一:手动解压JDK的压缩包,然后设置环境变量1.在/usr/目录下创建java目录..._linux 安装jdk-13.0.1

SQL SERVER学习(五)——CentOS7下安装SQL SERVER_1.1、通过yum,下载sql server的源;-程序员宅基地

文章浏览阅读3.2k次,点赞4次,收藏12次。官方文档:https://docs.microsoft.com/en-us/sql/linux/quickstart-install-connect-red-hatOS必须条件: Memory: 3.25 GBFile System: XFS or EXT4 (other file systems, such as BTRFS, are unsupported)Disk sp..._1.1、通过yum,下载sql server的源;