1340 - Story of Tomisu Ghost
| Time Limit: 2 second(s) | Memory Limit: 32 MB |
It is now 2150 AD and problem-setters are having a horrified time as the ghost of a problem-setter from the past, Mr. Tomisu, is frequently disturbing them. As always is the case in most common ghost stories, Mr. Tomisu has an unfulfilled dream: he had set 999 problems throughout his whole life but never had the leisure to set the 1000th problem. Being a ghost he cannot set problems now so he randomly asks problem-setters to complete one of his unfinished problems. One problem-setter tried to convince him saying that he should not regret as 999 is nowhere near 1024 (210) and he should not worry about power of 10 being an IT ghost. But the ghost slapped him hard after hearing this. So at last one problem setter decides to complete his problem:
"n! (factorial n) has at least t trailing zeroes in b based number system. Given the value of n and t, what is the maximum possible value of b?"
Input
Input starts with an integer T (≤ 4000), denoting the number of test cases.
Each case contains two integers n (1 < n ≤ 105) and t (0 < t ≤ 1000). Both n and t will be given in decimal (base 10).
Output
For each case, print the case number and the maximum possible value of b. Since b can be very large, so print b modulo 10000019. If such a base cannot be found then print -1 instead.
Sample Input |
Output for Sample Input |
|
4 1000 1000 1000 2 10 8 4 2 |
Case 1: -1 Case 2: 5227616 Case 3: 2 Case 4: 2 |
1 #include <cstdio>
2 #include <cstdlib>
3 #include <cstring>
4 #include <cmath>
5 #include <iostream>
6 #include <algorithm>
7 #include <map>
8 #include <queue>
9 #include <vector>
10 using namespace std;
11 typedef long long LL;
12 const int N=10000019;
13 bool prime[100005];
14 int ans_prime[100005];
15 int fen_prime[100005];
16 LL quick(LL n,LL m);
17 int main(void)
18 {
19 int i,j,k;
20 int an=0;
21 for(i=2; i<=100000; i++)
22 {
23 if(!prime[i])
24 {
25 for(j=i; ((LL)i*(LL)j)<=100000; j++)
26 {
27 prime[i*j]=true;
28 }
29 ans_prime[an++]=i;
30 }
31 }
32 int __ca=0;
33 scanf("%d",&k);
34 while(k--)
35 {
36 __ca++;
37 LL n,m;
38 scanf("%lld %lld",&n,&m);
39 memset(fen_prime,0,sizeof(fen_prime));
40 for(i=0; i<an; i++)
41 {
42 LL ask=n;
43 if(ask<ans_prime[i])
44 {
45 break;
46 }
47 else
48 {
49 while(ask)
50 {
51 fen_prime[i]+=ask/ans_prime[i];
52 ask/=ans_prime[i];
53 }
54 }
55 if(fen_prime[i]<m)
56 break;
57 }
58 LL anw=1;
59 for(i=0;i<an;i++)
60 {
61 if(fen_prime[i]<m)
62 {
63 break;
64 }
65 else
66 {
67 anw=(anw*quick(ans_prime[i],fen_prime[i]/m))%N;
68 }
69 }
70 printf("Case %d: ",__ca);
71 if(anw==1)
72 {
73 printf("-1\n");
74 }
75 else
76 {
77 printf("%lld\n",anw);
78 }
79 }
80 return 0;
81 }
82 LL quick(LL n,LL m)
83 {
84 LL ak=1;
85 while(m)
86 {
87 if(m&1)
88 {
89 ak=ak*n%N;
90 }
91 n=n*n%N;
92 m/=2;
93 }
94 return ak;
95 }
最新文章
- javascript 模式(2)——单例模式
- Export GridView Data to Excel. 从GridView导出数据到Excel的奇怪问题解析
- A Great Alchemist
- [python]使用virtualenv处理python版本问题
- Linux系统编程-防止僵尸进程产生的常用方法
- 学好Javascript是有方法的
- Memcache 在win7x64中安装配置
- adb shell top
- WebRTC Demo - getUserMedia()
- Hadoop MapReduce开发最佳实践（上篇）
- python 时间模块time，datetime详细介绍
- GYM 100608G 记忆化搜索+概率 2014-2015 Winter Petrozavodsk Camp, Andrew Stankevich Contest 47 (ASC 47)
- CentOS Linux搭建SVN服务器
- ORM框架SQLAlchemy
- C#基础知识总结(七)
- （转）MySQL慢查询分析优化 + MySQL调优
- sqlserver乱码问题解决
- Linux内核读书笔记第四周
- php实现共享内存进程通信函数之_shm
- getenv()函数