[已解决]【C++板块提升计划】梦想护卫舰 第33期 阶乘 & 鱼CR1 F题题解【原创】

zhangjinxuan

上一关：九连环

梦想护卫舰 第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

                               
登录/注册后可看大图

注：本题原创，链接：https://www.luogu.com.cn/problem/U287191

答案与解析

游客，如果您要查看本帖隐藏内容请回复

[/hide]

最佳战士排行榜

	第一名	第二名	第三名
名字
链接
语言
代码得分
奖励	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. 因为额度原因，部分鱼油可能下一天才能奖励。

                               
登录/注册后可看大图

想查看更多精彩内容，请访问 本专辑

创作不易，如果你喜欢，别忘了评分、顶


本关满意度调查

最佳答案

月排行榜 / 总排行榜

jhq999

2023-3-26 08:03:27

sfqxx 发表于 2023-3-25 16:53
嘿嘿

照葫芦画瓢弄了个3-3000000的，粗糙了点

#include <stdio.h>
int num[3000001][2],pnum[3000001][2],plen=1;
int fun(int n)
{
    if(num[n][0])
    {
        fun(num[n][0]);
        fun(num[n][1]);
    }
    else
    {
        pnum[num[n][1]][1]+=1;
    }
    return 0;
}
int main ()
{
    int i=0,j,k=0,m,s=2;
    num[1][0]=1;
    num[1][1]=1;
    for(i=2,k=1;i<=3000000;i+=1)
    {
      if(0==num[i][0])
      {

          pnum[k][0]=i;
          num[i][1]=k;
          k+=1;
      }
        for(j=1;j<i&&pnum[j][0]*i<=3000000;j+=1)
        {
            m=pnum[j][0]*i;
            num[m][0]=i;
            num[m][1]=pnum[j][0];

            if(0==i%pnum[j][0])break;
        }
    }
    plen=k;
    for(i=3;i<=3000000;i+=1)fun(i);
    for(i=1;i<plen;i+=1)if(pnum[i][1])printf("%d^%d*",pnum[i][0],pnum[i][1]);
    return 0;
}

跳转到最佳答案楼层

sfqxx

看看

sfqxx

有bug

#include <bits/stdc++.h>
using namespace std;

const int N = 10000000;
int n, m;
bool prime[N + 1];
int tot, c[N + 1], frac[N + 1], lastnum;
// c[i] means i-th prime
// prime[i] is prime if prime[i] equal to 0
// frac[i] means have how i.
// lastnum means last prime.

void init() {
        prime[1] = 1;
        for (int i = 2; i <= N; ++i) {
                if (!prime[i]) {
                        c[++tot] = i;
                }
                for (int j = 1; j <= tot && c[j] * i <= N; ++j) {
                        prime[c[j] * i] = 1;
                        if (i % c[j] == 0) break;
                }
        }
}

void solve(int i) {
        for (int j = 1; c[j] * c[j] <= i && j <= tot; ++j) {
                while (i % c[j] == 0) {
                        ++frac[c[j]];
                        i /= c[j];
                        lastnum = max(lastnum, c[j]);
                }
        }
        if (i > 1) {
                ++frac[i];
                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[c[i]]) {
                        printf("%d", c[i]);
                        if (frac[c[i]] != 1) {
                                printf("^%d", frac[c[i]]);
                        }
                        if (c[i] != lastnum) {
                                printf("*");
                        } else {
                                break;
                        }
                }
        }
        return 0;
}

zhangjinxuan

sfqxx 发表于 2023-3-25 16:39
有bug

scanf_s 是安全的读入，部分的C,C++编译器有，但洛谷似乎没有，感谢提出

sfqxx

嘿嘿

jhq999

sfqxx 发表于 2023-3-25 16:53
嘿嘿

照葫芦画瓢弄了个3-3000000的，粗糙了点

#include <stdio.h>
int num[3000001][2],pnum[3000001][2],plen=1;
int fun(int n)
{
    if(num[n][0])
    {
        fun(num[n][0]);
        fun(num[n][1]);
    }
    else
    {
        pnum[num[n][1]][1]+=1;
    }
    return 0;
}
int main ()
{
    int i=0,j,k=0,m,s=2;
    num[1][0]=1;
    num[1][1]=1;
    for(i=2,k=1;i<=3000000;i+=1)
    {
      if(0==num[i][0])
      {

          pnum[k][0]=i;
          num[i][1]=k;
          k+=1;
      }
        for(j=1;j<i&&pnum[j][0]*i<=3000000;j+=1)
        {
            m=pnum[j][0]*i;
            num[m][0]=i;
            num[m][1]=pnum[j][0];

            if(0==i%pnum[j][0])break;
        }
    }
    plen=k;
    for(i=3;i<=3000000;i+=1)fun(i);
    for(i=1;i<plen;i+=1)if(pnum[i][1])printf("%d^%d*",pnum[i][0],pnum[i][1]);
    return 0;
}

sfqxx

jhq999 发表于 2023-3-26 08:03
照葫芦画瓢弄了个3-3000000的，粗糙了点

WA

jhq999

sfqxx 发表于 2023-3-26 11:36
WA

#include <stdio.h>
int num[3000001][2],pnum[3000001][2],plen=1;
int fun(int n)
{
    if(num[n][0])
    {
        fun(num[n][0]);
        fun(num[n][1]);
    }
    else
    {
        pnum[num[n][1]][1]+=1;
    }
    return 0;
}
int main ()
{
    int i=0,j,k=0,n,m,s=2;
    num[1][0]=1;
    num[1][1]=1;
    for(i=2,k=1;i<=3000000;i+=1)
    {
      if(0==num[i][0])
      {

          pnum[k][0]=i;
          num[i][1]=k;
          k+=1;
      }
        for(j=1;j<i&&pnum[j][0]*i<=3000000;j+=1)
        {
            m=pnum[j][0]*i;
            num[m][0]=i;
            num[m][1]=pnum[j][0];

            if(0==i%pnum[j][0])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[i][1])
        {
            if(k)printf("*");
            k=1;
            if(pnum[i][1]>1)printf("%d^%d",pnum[i][0],pnum[i][1]);
            else printf("%d",pnum[i][0]);

        }
    }
    return 0;
}

sfqxx

jhq999 发表于 2023-3-26 12:21

AC

jhq999

sfqxx 发表于 2023-3-26 12:22
AC