ZOJ Monthly, June 2012 - K Factorial Problem in Base K - zoj 3621

2023-11-22 13:40

本文主要是介绍ZOJ Monthly, June 2012 - K Factorial Problem in Base K - zoj 3621,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

本场比赛,相对最好做的一题,看出本质,就容易了。

问题简化下,比如给你十进制数 s, 问 s! 末尾有几个0。我们一般都是直接找有多少个 2,5。因为2*5 = 10

那么 现在是 k进制数 s, 同理,就是找 s! 里面,有多少个因子的能够组成 k,最多组成 ans 个 k, ans 就是答案。

这个 自己可以简单证明下。后面好处理。

View Code
 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<cmath>
 6 using namespace std;
 7 #define N 65
 8 #define M 10010
 9 #define inf 2000000000
10 typedef long long LL;
11 char str[N];
12 LL k;
13 LL oksu(LL x) {
14     for (LL i = 2; i < x; ++i)
15         if (x % i == 0) return 0;
16     return 1;
17 }
18 LL solve(LL x, LL temp) {
19     LL y = x, ans = 0;
20     while (y <= temp) {
21         ans += temp / y;
22         if (temp/y < x) break;
23         y *= x;
24     }
25     return ans;
26 }
27 int main() {
28     while (scanf("%s%d", str, &k) != EOF) {
29         LL len = strlen(str);
30         LL s = 0;
31         for (LL i = 0; i < len; ++i) {
32             LL num;
33             if (str[i] <= 'z' && str[i] >= 'a') num = str[i]-'a'+36;
34             else if (str[i] <= 'Z' && str[i] >= 'A') num = str[i]-'A'+10;
35             else num = str[i]-'0';
36             s = num + s * k;
37         }
38         LL ans = -1;
39         for (LL i = 2;i <= k; ++i) {
40             if (k % i == 0 && oksu(i)){
41                 LL temp = k, bia = 0, x = 0;
42                 while(temp%i== 0) {
43                     temp /= i;
44                     bia++;
45                 }
46                 x = solve(i, s);
47                 if (ans == -1 || ans > x/bia)
48                     ans = x/bia;
49             }
50         }
51         printf("%lld\n", ans);
52     }
53     return 0;
54 }

转载于:https://www.cnblogs.com/slon/archive/2012/06/30/2571053.html

这篇关于ZOJ Monthly, June 2012 - K Factorial Problem in Base K - zoj 3621的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/410522

相关文章

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

uva 10025 The ? 1 ? 2 ? ... ? n = k problem(数学)

题意是    ?  1  ?  2  ?  ...  ?  n = k 式子中给k,? 处可以填 + 也可以填 - ,问最小满足条件的n。 e.g k = 12  - 1 + 2 + 3 + 4 + 5 + 6 - 7 = 12 with n = 7。 先给证明,令 S(n) = 1 + 2 + 3 + 4 + 5 + .... + n 暴搜n,搜出当 S(n) >=

数论ZOJ 2562

题意:给定一个数N,求小于等于N的所有数当中,约数最多的一个数,如果存在多个这样的数,输出其中最大的一个。 分析:反素数定义:对于任何正整数x,其约数的个数记做g(x).例如g(1)=1,g(6)=4.如果某个正整数x满足:对于任意i(0<i<x),都有g(i)<g(x),则称x为反素数。 性质一:一个反素数的质因子必然是从2开始连续的质数。 性质二:p=2^t1*3^t2*5^t3*7

zoj 1721 判断2条线段(完全)相交

给出起点,终点,与一些障碍线段。 求起点到终点的最短路。 枚举2点的距离,然后最短路。 2点可达条件:没有线段与这2点所构成的线段(完全)相交。 const double eps = 1e-8 ;double add(double x , double y){if(fabs(x+y) < eps*(fabs(x) + fabs(y))) return 0 ;return x + y ;

zoj 4624

题目分析:有两排灯,每排n个,每个灯亮的概率为p,每个灯之间互不影响,亮了的灯不再灭,问两排中,每排有大于等于m个灯亮的概率。 设dp[ i ][ j ]为第一排亮了i个灯,第二排亮了j个灯,距离目标状态的期望天数。显然 i >= m ,j >= m时 , dp[ i ][ j ] = 0 。 状态转移 : 第一排亮了a个灯,a 在[ 0 , n - i] 之间,第二排亮了b个灯 , b 在

zoj 3228 ac自动机

给出一个字符串和若干个单词,问这些单词在字符串里面出现了多少次。单词前面为0表示这个单词可重叠出现,1为不可重叠出现。 Sample Input ab 2 0 ab 1 ab abababac 2 0 aba 1 aba abcdefghijklmnopqrstuvwxyz 3 0 abc 1 def 1 jmn Sample Output Case 1 1 1 Case 2

ZOJ Monthly, August 2014小记

最近太忙太忙,只能抽时间写几道简单题。不过我倒是明白要想水平提高不看题解是最好的了。 A  我只能死找规律了,无法证明 int a[50002][2] ;vector< vector<int> > gmax , gmin ;int main(){int n , i , j , k , cmax , cmin ;while(cin>>n){/* g

docker学习系列(四)制作基础的base项目镜像--jdk+tomcat

前面已经完成了docker的安装以及使用,现在我们要将自己的javaweb项目与docker结合 1.1准备jdk+tomcat软件 ​​我下载了apache-tomcat-7.0.68.tar.gz和jdk-7u79-linux-x64.tar.gz,存储于Linux机器的本地目录/usr/ect/wt/下(利用xshell上传)。利用linux命令 tar -zxvf apache-tom

ZOJ 3324 Machine(线段树区间合并)

这道题网上很多代码是错误的,由于后台数据水,他们可以AC。 比如这组数据 10 3 p 0 9 r 0 5 r 6 9 输出应该是 0 1 1 所以有的人直接记录该区间是否被覆盖过的方法是错误的 正确方法应该是记录这段区间的最小高度(就是最接近初始位置的高度),和最小高度对应的最长左区间和右区间 开一个sum记录这段区间最小高度的块数,min_v 记录该区间最小高度 cover

11991 - Easy Problem from Rujia Liu?

题意: 输入一串整型数列,再输入两个数k,v,输出第k个v的序号。不存在则输出0,如第一个样例 8 41 3 2 2 4 3 2 11 3 //第1个3,序号为2,输出22 4 //第2个4,不存在,输出03 2 //第3个2,序号为7,输出74 2 思路: struct num {