外国人做的网站,app网站制作下载,室内设计师接单网,wordpress验证登录页面链接#xff1a;
时间限制#xff1a;C/C 1秒#xff0c;其他语言2秒
空间限制#xff1a;C/C 262144K#xff0c;其他语言524288K
64bit IO Format: %lld题目描述 给定一个正整数 p 求一个最小的正整数 n#xff0c;使得 n! 是 p 的倍数 输入描述: 第一行输入一个正整数…链接
时间限制C/C 1秒其他语言2秒
空间限制C/C 262144K其他语言524288K
64bit IO Format: %lld题目描述 给定一个正整数 p 求一个最小的正整数 n使得 n! 是 p 的倍数 输入描述: 第一行输入一个正整数T表示测试数据组数 接下来T行每行一个正整数p 输出描述: 输出T行对于每组测试数据输出满足条件的最小的n 示例1 输入
4
1
2
4
8输出
1
2
4
4备注: T≤103,p≤109 题解 两个方法 二分与贪心
在什么条件下n!会是p的倍数呢 n!的素因子集合包含p的素因子集合也就是对于每个质因子阶乘n中的数量大于对应p中的数量
贪心
暴力做法从2开始循环质因数对于每次一个质因数i看p1当前能分解出多少个然后再枚举n,看n最小为多少能做到质因数i的数量大于等于p1 代码中有句summax(sum,j);什么含义你想如果我们之前求出n9包含3的数量满足条件那枚举5时得到n1010的阶乘是包含9的阶乘也就是10既满足质因数2也满足3所以求最大max 代码内也有注释
代码
#includebits/stdc.h
using namespace std;
int main() {int t,p1,sum0;cint;while(t--) {cinp1;sum0;for(int i2;i*ip1;i)if(p1%i0) {int cnt0;while(p1%i0) {p1/i;cnt;}//当前质因子i在p1中的数量 int tmp0;int j;for(ji;;ji) {int nj;while(n%i0){n/i;tmp;} //记录当前质因数在n中的数量 if(tmpcnt) break;//找到一个数使得他的质因数i的数量多于等于p1 }summax(sum,j); // coutsumendl;}coutmax(sum,p1)endl;}
}二分
其实就是把方法一中暴力的过程改成更为巧妙的二分过程先将p1的质因数存入数组prime然后二分查找寻找最小的n满足他的质因数i的数量多于等于p1 代码借鉴其大佬博客写的
代码
#include bits/stdc.h
using namespace std;const int maxn 1e5 3;
int prime[maxn], cnt[maxn], len 0;
//素因子素因子的个数数组长度int judge(int mid) {for (int i 1; i len; i){int n midint sum 0;while (n) {sum n / prime[i];n / prime[i];}if (sum cnt[i]) return 0;//不满足条件就找下一个n }return 1;//满足要求
}
int main() {int T; cinT;int l,r,sum; while (T--) {int p1;cinp1;len 0;memset(cnt, 0, sizeof cnt);for (int i 2; i * i p1; i)if ( p1 % i0) {prime[len] i;while (p1 % i0) {cnt[len];p1 / i;}}if (p1 1) {prime[len] p1;cnt[len];}//求出素因子及其个数l 1, r 1e9, sum 0;while (l r) {int mid l r 1;if (judge(mid)) {r mid - 1;sum mid;}else l mid 1; }//二分查找printf(%d\n, sum);}return 0;
}
