LightOJ 1282 Leading and Trailing 数论

题目大意：求n^k的前三位数和后三位数。

题目思路：后三位数直接用快速幂取模就行了，前三位则有些小技巧：

对任意正数都有n=10^T(T可为小数)，设T=x+y，则n=10^(x+y)=10^x*10^y，其中10^x为10的整倍数（x为整数确定数位长度），所以主要求出10^y的值。

T=log10（n^k）=klog10（n），可以调用fmod函数求其小数部分即y值。

#include<iostream>

#include<algorithm>

#include<cstring>

#include<vector>

#include<stdio.h>

#include<queue>

#include<math.h>

#define INF 0x3f3f3f3f

#define MAX 1000005

#define Temp 1000000000

using namespace std;

long long Pow(long long n,long long m)//快速幂取模

{

    long long ans=;

    while(m)

    {

        if(m&)

        {

            ans=ans*n%;

        }

        n=(n*(n%))%;

        m/=;

    }

    return ans;

}

int main()

{

    long long cnt=,T;

    long long n,m;

    scanf("%lld",&T);

    while(T--)

    {

        scanf("%lld%lld",&n,&m);

        long long S=Pow(n,m);

        long long E=(pow(10.0,2.0+fmod((double)m*(log10(double(n))),))+1e-);//注意精度问题

        printf("Case %lld: %lld %03lld\n",cnt++,E,S);

    }

    return ;

}

巴特西

LightOJ 1282 Leading and Trailing 数论

最新文章

热门文章