首页 > 代码库 > poj 2720 Last Digits
poj 2720 Last Digits
Last Digits
Description Exponentiation of one integer by another often produces very large results. In this problem, we will compute a function based on repeated exponentiation, but output only the last n digits of the result. Doing this efficiently requires careful thought about how to avoid computing the full answer. Given integers b, n, and i, we define the function f(x) recursively by f(x) = bf(x-1) if x > 0, and f(0)=1. Your job is to efficiently compute the last n decimal digits of f(i). Input The input consists of a number of test cases. Each test case starts with the integer b (1 <= b <= 100) called the base. On the next line is the integer i (1 <= i <= 100) called the iteration count. And finally, the last line contains the number n (1 <= n <= 7), which is the number of decimal digits to output. The input is terminated when b = 0. Output For each test case, print on one line the last n digits of f(i) for the base b specified. If the result has fewer than n digits, pad the result with zeroes on the left so that there are exactly n digits. Sample Input 2471010631070 Sample Output 00655360000004195387 Source Rocky Mountain 2005 |
/** @Author: Lyucheng* @Date: 2017-08-07 15:47:29* @Last Modified by: Lyucheng* @Last Modified time: 2017-08-07 20:10:43*//* 题意：定义一个函数f(i)=b^(f(i-1)),给你b,i,n让你求f(i)的后n位，不足的用前导零补充 思路：后n位就是f(n)%(10^n) 问题：超时...打表LL b,n,i;LL mod;char str[10];LL pos;char format[] = "%00d\n";inline LL power(LL a,LL b,LL mod){//a的b次方 if(b==0) return 1; LL cnt=power(a,b/2,mod); cnt=cnt*cnt%mod; if(b%2==1) cnt=cnt*a%mod; return cnt; }// return f(x)%modinline LL fun(LL b,LL x,LL mod){ if(x==0) return 1LL;//如果是0次，那么就是1 else{ LL res=power(b,fun(b,x-1,mod),mod); if(res==0) res=mod; return res; }}*/#include <stdio.h>#include <string.h>#include <iostream>#include <algorithm>#include <vector>#include <queue>#include <set>#include <map>#include <string>#include <math.h>#include <stdlib.h>#include <time.h>using namespace std;int a[111][12]={{0,1,1,1,1,1,1,1,1,1,1,1,},{0,2,4,16,65536,9156736,7428736,1748736,948736,2948736,2948736,2948736,},{0,3,27,7484987,739387,355387,6595387,195387,4195387,4195387,4195387,4195387,},{0,4,256,6084096,1392896,4208896,5328896,3728896,1728896,1728896,1728896,1728896,},{0,5,3125,8203125,8203125,8203125,8203125,8203125,8203125,8203125,8203125,8203125,},{0,6,46656,3878656,8438656,3238656,7238656,7238656,7238656,7238656,7238656,7238656,},{0,7,823543,132343,3172343,5172343,5172343,5172343,5172343,5172343,5172343,5172343,},{0,8,6777216,1126656,9449856,7945856,6825856,3225856,5225856,5225856,5225856,5225856,},{0,9,7420489,7177289,5865289,1945289,4745289,2745289,2745289,2745289,2745289,2745289,},{0,10,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,},{0,11,1670611,2906611,7066611,6666611,2666611,2666611,2666611,2666611,2666611,2666611,},{0,12,448256,5094016,7596416,4172416,2412416,12416,4012416,4012416,4012416,4012416,},{0,13,6592253,8549053,4325053,4645053,7045053,5045053,5045053,5045053,5045053,5045053,},{0,14,5558016,4651136,8510336,782336,2302336,5502336,7502336,7502336,7502336,7502336,},{0,15,859375,859375,859375,859375,859375,859375,859375,859375,859375,859375,},{0,16,9551616,255616,15616,4415616,415616,415616,415616,415616,415616,415616,},{0,17,6764177,4229777,9125777,6485777,4085777,85777,85777,85777,85777,85777,},{0,18,7575424,542976,2395776,6315776,4315776,4315776,4315776,4315776,4315776,4315776,},{0,19,9123979,459179,3483179,2363179,7963179,9963179,9963179,9963179,9963179,9963179,},{0,20,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,},{0,21,1124421,4492421,5452421,6652421,652421,652421,652421,652421,652421,652421,},{0,22,6723584,7785856,3092096,8608896,8784896,1104896,3504896,1504896,1504896,1504896,},{0,23,2910567,4988647,1606247,9078247,4918247,9718247,5718247,5718247,5718247,5718247,},{0,24,2843776,8014976,4734976,6734976,6734976,6734976,6734976,6734976,6734976,6734976,},{0,25,7265625,7265625,7265625,7265625,7265625,7265625,7265625,7265625,7265625,7265625,},{0,26,203776,4203776,4203776,4203776,4203776,4203776,4203776,4203776,4203776,4203776,},{0,27,9892803,403683,7450083,1242083,7002083,9802083,3802083,3802083,3802083,3802083,},{0,28,5812736,2791296,8986496,3370496,2650496,250496,2250496,2250496,2250496,2250496,},{0,29,6483469,3310669,3646669,1326669,9726669,1726669,1726669,1726669,1726669,1726669,},{0,30,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,},{0,31,4734431,9246431,5006431,9806431,3806431,3806431,3806431,3806431,3806431,3806431,},{0,32,2542976,1314176,1074176,9074176,9074176,9074176,9074176,9074176,9074176,9074176,},{0,33,3380513,3623713,1111713,9031713,1831713,3831713,3831713,3831713,3831713,3831713,},{0,34,9569536,8863616,9874816,9842816,1362816,4162816,6162816,6162816,6162816,6162816,},{0,35,5546875,8046875,8046875,8046875,8046875,8046875,8046875,8046875,8046875,8046875,},{0,36,9291136,6747136,4507136,4107136,107136,107136,107136,107136,107136,107136,},{0,37,9442517,9296917,4528917,9488917,8288917,2288917,2288917,2288917,2288917,2288917,},{0,38,4610304,9627136,4242816,3094016,4102016,822016,5622016,7622016,7622016,7622016,},{0,39,9951959,9516759,6028759,1308759,4508759,2508759,2508759,2508759,2508759,2508759,},{0,40,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,},{0,41,7953641,4977641,5137641,9537641,5537641,5537641,5537641,5537641,5537641,5537641,},{0,42,3016064,1994496,1891456,5904256,4608256,3328256,2928256,928256,928256,928256,},{0,43,8995507,561107,4801107,801107,801107,801107,801107,801107,801107,801107,},{0,44,9367296,1165056,7577856,1961856,3481856,9081856,7081856,7081856,7081856,7081856,},{0,45,3828125,8828125,8828125,8828125,8828125,8828125,8828125,8828125,8828125,8828125,},{0,46,3181696,3229696,8989696,189696,4189696,4189696,4189696,4189696,4189696,4189696,},{0,47,5062863,4457423,7123023,8579023,1139023,6739023,2739023,2739023,2739023,2739023,},{0,48,2403456,6161536,7054336,3102336,2782336,1582336,9582336,9582336,9582336,9582336,},{0,49,5062449,2182449,8182449,8182449,8182449,8182449,8182449,8182449,8182449,8182449,},{0,50,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,},{0,51,1315051,5815051,5815051,5815051,5815051,5815051,5815051,5815051,5815051,5815051,},{0,52,7575296,3348736,7691136,7595136,7435136,3835136,7835136,7835136,7835136,7835136,},{0,53,6150373,6305573,6977573,6897573,8097573,97573,97573,97573,97573,97573,},{0,54,3789056,167296,5332096,1028096,2948096,1348096,9348096,9348096,9348096,9348096,},{0,55,5234375,5234375,5234375,5234375,5234375,5234375,5234375,5234375,5234375,5234375,},{0,56,323456,3315456,8275456,3075456,7075456,7075456,7075456,7075456,7075456,7075456,},{0,57,5688057,9688057,9688057,9688057,9688057,9688057,9688057,9688057,9688057,9688057,},{0,58,1097984,9904896,1190656,6179456,7523456,6243456,9843456,7843456,7843456,7843456,},{0,59,2427939,8732739,540739,8220739,1020739,9020739,9020739,9020739,9020739,9020739,},{0,60,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,},{0,61,431661,9207661,2567661,2167661,8167661,8167661,8167661,8167661,8167661,8167661,},{0,62,4466944,5959936,6879616,674816,402816,8322816,7122816,9122816,9122816,9122816,},{0,63,8342847,4850367,4123967,4171967,6811967,2011967,8011967,8011967,8011967,8011967,},{0,64,306816,8398336,8465536,7057536,4177536,7377536,9377536,9377536,9377536,9377536,},{0,65,7890625,7890625,7890625,7890625,7890625,7890625,7890625,7890625,7890625,7890625,},{0,66,3244416,4988416,7548416,1948416,7948416,7948416,7948416,7948416,7948416,7948416,},{0,67,2277723,3133563,535163,7319163,1479163,9879163,5879163,5879163,5879163,5879163,},{0,68,3733376,6677376,8677376,8677376,8677376,8677376,8677376,8677376,8677376,8677376,},{0,69,1741429,1912629,7416629,1096629,6696629,8696629,8696629,8696629,8696629,8696629,},{0,70,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,},{0,71,9996471,6924471,5484471,6684471,684471,684471,684471,684471,684471,684471,},{0,72,2313216,3421696,6007296,2839296,5879296,4679296,679296,679296,679296,679296,},{0,73,2013833,6922633,5866633,2586633,6186633,4186633,4186633,4186633,4186633,4186633,},{0,74,6312576,7666176,8146176,2146176,2146176,2146176,2146176,2146176,2146176,2146176,},{0,75,4921875,7421875,7421875,7421875,7421875,7421875,7421875,7421875,7421875,7421875,},{0,76,4552576,2552576,2552576,2552576,2552576,2552576,2552576,2552576,2552576,2552576,},{0,77,996797,3587197,8115197,9075197,6275197,275197,275197,275197,275197,275197,},{0,78,3454464,2576256,3799296,1780096,8196096,2516096,8916096,6916096,6916096,6916096,},{0,79,9775919,6787119,4003119,8883119,7283119,9283119,9283119,9283119,9283119,9283119,},{0,80,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,},{0,81,1782481,54481,2214481,7014481,1014481,1014481,1014481,1014481,1014481,1014481,},{0,82,8388224,6066176,4472576,2952576,8952576,8952576,8952576,8952576,8952576,8952576,},{0,83,2640587,2904427,3294827,6718827,2158827,8558827,2558827,2558827,2558827,2558827,},{0,84,9118336,7058816,3382016,4470016,2390016,5190016,7190016,7190016,7190016,7190016,},{0,85,4453125,9453125,9453125,9453125,9453125,9453125,9453125,9453125,9453125,9453125,},{0,86,6935936,8631936,9591936,9191936,5191936,5191936,5191936,5191936,5191936,5191936,},{0,87,4601383,632103,6670503,7918503,8478503,1678503,5678503,5678503,5678503,5678503,},{0,88,9786496,5698816,7919616,7871616,8751616,5951616,3951616,3951616,3951616,3951616,},{0,89,2384409,3741209,9373209,1053209,4253209,2253209,2253209,2253209,2253209,2253209,},{0,90,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,},{0,91,6642691,8006691,4966691,9366691,5366691,5366691,5366691,5366691,5366691,5366691,},{0,92,3364736,4237056,2262656,7910656,7750656,4950656,950656,950656,950656,950656,},{0,93,6482893,7002893,5002893,5002893,5002893,5002893,5002893,5002893,5002893,5002893,},{0,94,1956096,6944256,7021056,6285056,5005056,605056,8605056,8605056,8605056,8605056,},{0,95,9609375,9609375,9609375,9609375,9609375,9609375,9609375,9609375,9609375,9609375,},{0,96,7162496,170496,9530496,730496,4730496,4730496,4730496,4730496,4730496,4730496,},{0,97,5744737,2058337,4922337,6282337,2682337,8682337,8682337,8682337,8682337,8682337,},{0,98,1295744,3961216,7748736,4263936,1015936,4535936,9735936,1735936,1735936,1735936,},{0,99,499899,7479899,5479899,5479899,5479899,5479899,5479899,5479899,5479899,5479899,},{0,100,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,},};int b,i,n;int main(){ // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); while(scanf("%d",&b)!=EOF&&b){ scanf("%d%d",&i,&n); string s=""; int pos=a[b-1][(i>11?11:i)]; for(int i=0;i<n;i++){ s+=pos%10+‘0‘; pos/=10; } while(n--){ cout<<s[n]; }cout<<endl; } return 0;}
poj 2720 Last Digits
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。