首页 > 代码库 > LightOJ - 1282 Leading and Trailing (数论)

LightOJ - 1282 Leading and Trailing (数论)

题意:求nk的前三位和后三位。

分析:

1、后三位快速幂取模,注意不足三位补前导零。

补前导零:假如nk为1234005,快速幂取模后,得到的数是5,因此输出要补前导零。

2、前三位:

令n=10a,则nk=10ak=10x+y,x为ak的整数部分,y为ak的小数部分。

eg:n=19,k=4,则nk=130321,

a=log10(n)=1.2787536009528289615363334757569

ak=5.1150144038113158461453339030277,

因此,x=5,y=0.1150144038113158461453339030277,

10y=1.3032099999999999999999999999999,因此要获得前三位只需要10y*100下取整即可。

3、注意:

log(double x)---底数为e

log10(double x)---底数为10

没有底数为2的函数,因此可log10(x)/log10(2)。

#include<cstdio>#include<algorithm>#include<cmath>using namespace std;int POW_MOD(int n, int k, int MOD){    if(k == 0) return 1 % MOD;    int tmp = POW_MOD(n, k >> 1, MOD);    long long ans = (tmp * tmp) % MOD;    if(k & 1) (ans *= (n % MOD)) %= MOD;    return ans;}int main(){    int T;    scanf("%d", &T);    int kase = 0;    while(T--){        int n, k;        scanf("%d%d", &n, &k);        int x = (int)(pow(10.0, fmod(log10(n * 1.0) * k, (int)(log10(n * 1.0) * k))) * 100);        int y = POW_MOD(n, k, 1000);        printf("Case %d: %d %03d\n", ++kase, x, y);    }    return 0;}

  

LightOJ - 1282 Leading and Trailing (数论)