Codeforces1114C. Trailing Loves (or L'oeufs?)-(质因子分解)
2024-09-17 18:14:28
题目大意:
求n!转化为b进制后后导0的个数
思路:
我们首先考虑十进制转化为二进制者后,后导0的个数如何求
十进制数num
y = num%2
num/=2
如果y为0则,该位为0,就是求num能连续除以几次2(在整除的条件下)
十进制是num,进制为b
我们可以采取同样的思路
但是!
这里n!太大了,没法直接算出来
我们采取分解质因子的方式
同时我们对b也分解质因子(因为num要包含整个的b,如果b分解质因子之后的每一项都包含,则说明有整除关系)
n! --> a1[i]^b1[i] * a2[i]^b2[i] * a3[i]*b3[i]
b --> c1[i]^d1[i] * c2[i]^d2[i] * c3[i]*d3[i]
对b的每项在N!中查找包含了几个,取min就是答案
注意爆long long
Code:
ll n, b, ans = 1e18;
ll cal(ll t, ll temp)
{
ll res = 0;
ll nn = n;
for(ll i = t; i <= n ; i *= t)
{
res += (n / i);
if(i*t >n) break;
}
return res / temp;
}
void solve(ll num)
{
for(ll i = 1 ; i <= x ; i++)
{
ll t = p[i];
if(t > num) break;
ll temp = 0;
while(num % t == 0)
{
num /= t;
temp++;
}
if(temp) ans = min(ans, cal(t, temp));
}
if(num > 1) ans = min(ans, cal(num, 1));
}
int main()
{
oula();
n = read(), b = read();
solve(b);
out(ans);
return 0;
}
最新文章
- IOS textField(textview)字数判断
- python学习笔记-(九)模块
- RabbitMQ消息队列:ACK机制
- cocos2d 中判断CGPoint或者CGSize是否相等
- YBC中国国际青年创业计划
- 类作为返回类型 ,具有java特点-封装等 而且应用起来很方便。
- 2014 CSDN博文大赛终于获奖名单发布
- Directx11学习笔记【十八】 Blending混合
- Caffe-5.2-(GPU完整流程)训练(依据googlenet微调)
- 解读Scrum燃尽图
- Kali Linux搭建Go语言环境
- 四、Python-元组
- 雷林鹏分享:XML Parser
- iOS手势的综合运用
- Redis学习之(一)
- CH1809匹配统计【KMP】
- 001Spring Boot中使用MongoDB
- linux 打包和压缩文件
- 常用移动web开发框架--转载
- 2011-03-17免Oracle客户端连远程Oracle的方法
热门文章
- npm-run-all
- taro demos &; taro 组件库
- lms微服务框架介绍
- postman功能介绍
- 02.Fancy Indexing
- CSS中Position属性static、absolute、fixed、relative
- Vue学习笔记-Vue.js-2.X 学习(二)===>;组件化开发
- 微信小程序:将yyyy-mm-dd格式的日期转换成yyyy-mm-dd hh:mm:ss格式的日期
- 微信小程序:解决小程序中有些格式如webpiPhone手机暂不支持的问题
- hive复杂数据类型的用法