【C++板块提升计划】梦想护卫舰 第33期 阶乘 & 鱼CR1 F题题解【原创】
本帖最后由 zhangjinxuan 于 2023-3-25 16:49 编辑上一关：九连环
梦想护卫舰 第33期 九连环 & 鱼CR1 F题题解
题目描述
给你两个数字 n 和 m，问 n!/m! 的质因数分解是多少 （保证 n > m)
输入格式
两个数字 n, m
输出格式
输出格式有点复杂，请让我慢慢道来
举个例子，因为 9!/6!=504
输出的内容就是：
2^3*3^2*7
用另一种语言描述就是我们4设一个数有 m 个 n 个质因数，输出的内容必须包含 n ^ m，如果 m=1，直接输出 n，且 m 不可以等于 0
最后，要注意没有空格，所有质因数也要从小到大排序
输入样例1
9 6
输出样例1
2^3*3^2*7
输入样例2
10 5
输出样例2
2^5*3^3*5*7
数据范围
对于 100% 的数据，保证 1<=m<n<=3*10^6
static/image/hrline/1.gif
注：本题原创，链接：https://www.luogu.com.cn/problem/U287191
答案与解析
**** Hidden Message *****
最佳战士排行榜
|第一名|第二名|第三名
名字|||
链接|||
语言|||
代码得分|||
奖励|5鱼币5荣誉+“最佳答案”|3鱼币3荣誉|2鱼币2荣誉
我们一起来 Hack
Hack 规则
1. Hack 经证实均有奖励，你在 Hack 时得提供完整证据、证明;
2. 在本关，支持题面 hack，标程 hack，细节问题奖励 1~5 鱼币，重点问题奖励 5~10 鱼币
3. 奖励上限为 3 次
名字|sfqxx
Hack 类型|标程hack(环境差异)
是否证实|是
奖励|2鱼币
答题/奖励规则
1. 不能抄袭，否则无奖励，可能还会扣分;
2. 当您遇到问题时，您可以回贴提问，我会为您解答
3. 提供完整能得分的题解，均有奖励。
4. 因为额度原因，部分鱼油可能下一天才能奖励。
static/image/hrline/1.gif
想查看更多精彩内容，请访问 本专辑
创作不易，如果你喜欢，别忘了评分、顶{:10_281:}
本关满意度调查 看看 有bug#include <bits/stdc++.h>
using namespace std;
const int N = 10000000;
int n, m;
bool prime;
int tot, c, frac, lastnum;
// c means i-th prime
// prime is prime if prime equal to 0
// frac means have how i.
// lastnum means last prime.
void init() {
prime = 1;
for (int i = 2; i <= N; ++i) {
if (!prime) {
c[++tot] = i;
}
for (int j = 1; j <= tot && c * i <= N; ++j) {
prime * i] = 1;
if (i % c == 0) break;
}
}
}
void solve(int i) {
for (int j = 1; c * c <= i && j <= tot; ++j) {
while (i % c == 0) {
++frac];
i /= c;
lastnum = max(lastnum, c);
}
}
if (i > 1) {
++frac;
lastnum = max(lastnum, i);
}
}
int main() {
scanf("%d%d", &n, &m);
init();
scanf("%d", &n); //应该是scanf,不是scanf_s
for (int i = m + 1; i <= n; ++i) {
solve(i);
}
for (int i = 1; i <= tot; ++i) {
if (frac]) {
printf("%d", c);
if (frac] != 1) {
printf("^%d", frac]);
}
if (c != lastnum) {
printf("*");
} else {
break;
}
}
}
return 0;
} sfqxx 发表于 2023-3-25 16:39
有bug
scanf_s 是安全的读入，部分的C,C++编译器有，但洛谷似乎没有，感谢提出 嘿嘿 本帖最后由 jhq999 于 2023-3-26 08:28 编辑
sfqxx 发表于 2023-3-25 16:53
嘿嘿
照葫芦画瓢弄了个3-3000000的，粗糙了点
#include <stdio.h>
int num,pnum,plen=1;
int fun(int n)
{
if(num)
{
fun(num);
fun(num);
}
else
{
pnum]+=1;
}
return 0;
}
int main ()
{
int i=0,j,k=0,m,s=2;
num=1;
num=1;
for(i=2,k=1;i<=3000000;i+=1)
{
if(0==num)
{
pnum=i;
num=k;
k+=1;
}
for(j=1;j<i&&pnum*i<=3000000;j+=1)
{
m=pnum*i;
num=i;
num=pnum;
if(0==i%pnum)break;
}
}
plen=k;
for(i=3;i<=3000000;i+=1)fun(i);
for(i=1;i<plen;i+=1)if(pnum)printf("%d^%d*",pnum,pnum);
return 0;
}
jhq999 发表于 2023-3-26 08:03
照葫芦画瓢弄了个3-3000000的，粗糙了点
WA sfqxx 发表于 2023-3-26 11:36
WA
#include <stdio.h>
int num,pnum,plen=1;
int fun(int n)
{
if(num)
{
fun(num);
fun(num);
}
else
{
pnum]+=1;
}
return 0;
}
int main ()
{
int i=0,j,k=0,n,m,s=2;
num=1;
num=1;
for(i=2,k=1;i<=3000000;i+=1)
{
if(0==num)
{
pnum=i;
num=k;
k+=1;
}
for(j=1;j<i&&pnum*i<=3000000;j+=1)
{
m=pnum*i;
num=i;
num=pnum;
if(0==i%pnum)break;
}
}
plen=k;
scanf("%d%d",&n,&m);
for(i=m+1;i<=n;i+=1)fun(i);
for(i=1,k=0;i<plen;i+=1)
{
if(pnum)
{
if(k)printf("*");
k=1;
if(pnum>1)printf("%d^%d",pnum,pnum);
else printf("%d",pnum);
}
}
return 0;
}
jhq999 发表于 2023-3-26 12:21
AC sfqxx 发表于 2023-3-26 12:22
AC
{:5_109:}
页:
[1]