前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >数论(一)LOJ1282

数论(一)LOJ1282

作者头像
Enterprise_
发布2019-02-21 17:17:20
3130
发布2019-02-21 17:17:20
举报
文章被收录于专栏:小L的魔法馆

1.题目来源LOJ1282

You are given two integers: n and k, your task is to find the most significant three digits, and least significant three digits 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 leading digits (most significant) and three trailing digits (least significant). You can assume that the input is given such that nk contains at least 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

2.题目分析

给定两个整数n和k,求出n^k的前三位和后三位

3.我的思路

虽然好像数据很大哦,估计要爆炸,但是要不要用java试一下呢 TLE代码如下:

代码语言:javascript
复制
import java.math.BigDecimal;
import java.util.Scanner;
import java.util.HashMap;
import java.math.BigInteger;
public class Main{
public static void main(String[] args) {
    Scanner ind = new Scanner(System.in);
    int T=ind.nextInt(),d=1;
    while(T>1){
    --T;
    BigInteger a=ind.nextBigInteger();
    int k=ind.nextInt();
    BigInteger res=BigInteger.valueOf(1);
    while(k>=1){
    if(k%2==1)
    {
        res=res.multiply(a);
        k--;
    }
    k=k/2;
    a=a.multiply(a);
}
String s=res.toString();
System.out.print("Case ");
System.out.print(d);
d++;
System.out.print(": ");
System.out.print(s.substring(0, 3));
System.out.print(" ");
System.out.println(s.substring(s.length()-3, s.length()));
}
}
}

咳咳……结果还是爆了,还是没办法想的简单Orz.

LOJ1282
LOJ1282

好吧,其实换一种思路,不用把结构都求出来,只求前三位和后三位。 先看后三位,这个可以使用快速幂来做,模取1000即可。 关键是前三位: 推导过程如下:

这里写图片描述
这里写图片描述
这里写图片描述
这里写图片描述

所以最后,x的前m位数就为10m−1∗10b10m−1∗10b10^{m-1}*10^{b} 图片来自http://blog.csdn.net/Dylan_Frank/article/details/52749665?locationNum=16 最后的最后,由于把整数和小数分开了,结果就可能出现00*或者0**,所以需要去掉前导零,就用%3d,要不还是WA…..Orz

代码语言:javascript
复制
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstdio>
using namespace std;
int Pow_mod(int a, int b, int mod) {
    int res = 1, temp;
    a = a%mod, temp = a;
    for (; b; b /= 2) {
        if (b & 1) {
            res = res * temp % mod; // 2进制上这一位为1,乘上这一位权值
        }
        temp = temp * temp % mod; // 位数加1, 权值平方
    }
    return res;
}
int main()
{
    int n, k, T, count = 1;
    cin >> T;
    while (T-- > 0)
    {
        cin >> n >> k;
        double a = k*log10(n);
        a = a - (int)a;
        double res1 = pow(10, a)*pow(10, 2);
        int  res2 = Pow_mod(n, k, 1000);
        printf("Case %d: %d %03d\n",count,(int)res1,res2);
        count++;
    }
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2018年03月19日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 1.题目来源LOJ1282
  • 2.题目分析
  • 3.我的思路
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档