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

zhangjinxuan

上一关：九连环

梦想护卫舰 第33期 九连环 & 鱼CR1 F题题解

题目描述

给你两个数字 n 和 m，问 n!/m! 的质因数分解是多少 （保证 n > m)

输入格式
两个数字 n, m

输出格式

输出格式有点复杂，请让我慢慢道来

举个例子，因为 9!/6!=504

输出的内容就是：

1. 
   
2. 2^3*3^2*7

复制代码

用另一种语言描述就是我们4设一个数有 m 个 n 个质因数，输出的内容必须包含 n ^ m，如果 m=1，直接输出 n，且 m 不可以等于 0

最后，要注意没有空格，所有质因数也要从小到大排序

输入样例1

1. 9 6

复制代码

输出样例1

1. 2^3*3^2*7

复制代码

输入样例2

1. 10 5

复制代码

输出样例2

1. 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的，粗糙了点

1. #include <stdio.h>
   
2. int num[3000001][2],pnum[3000001][2],plen=1;
   
3. int fun(int n)
   
4. {
   
5.     if(num[n][0])
   
6.     {
   
7.         fun(num[n][0]);
   
8.         fun(num[n][1]);
   
9.     }
   
10.     else
    
11.     {
    
12.         pnum[num[n][1]][1]+=1;
    
13.     }
    
14.     return 0;
    
15. }
    
16. int main ()
    
17. {
    
18.     int i=0,j,k=0,m,s=2;
    
19.     num[1][0]=1;
    
20.     num[1][1]=1;
    
21.     for(i=2,k=1;i<=3000000;i+=1)
    
22.     {
    
23.       if(0==num[i][0])
    
24.       {
    
25. 
    
26.           pnum[k][0]=i;
    
27.           num[i][1]=k;
    
28.           k+=1;
    
29.       }
    
30.         for(j=1;j<i&&pnum[j][0]*i<=3000000;j+=1)
    
31.         {
    
32.             m=pnum[j][0]*i;
    
33.             num[m][0]=i;
    
34.             num[m][1]=pnum[j][0];
    
35. 
    
36.             if(0==i%pnum[j][0])break;
    
37.         }
    
38.     }
    
39.     plen=k;
    
40.     for(i=3;i<=3000000;i+=1)fun(i);
    
41.     for(i=1;i<plen;i+=1)if(pnum[i][1])printf("%d^%d*",pnum[i][0],pnum[i][1]);
    
42.     return 0;
    
43. }
    

复制代码

跳转到最佳答案楼层

sfqxx

看看

sfqxx

有bug

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. const int N = 10000000;
   
5. int n, m;
   
6. bool prime[N + 1];
   
7. int tot, c[N + 1], frac[N + 1], lastnum;
   
8. // c[i] means i-th prime
   
9. // prime[i] is prime if prime[i] equal to 0
   
10. // frac[i] means have how i.
    
11. // lastnum means last prime.
    
12. 
    
13. void init() {
    
14.         prime[1] = 1;
    
15.         for (int i = 2; i <= N; ++i) {
    
16.                 if (!prime[i]) {
    
17.                         c[++tot] = i;
    
18.                 }
    
19.                 for (int j = 1; j <= tot && c[j] * i <= N; ++j) {
    
20.                         prime[c[j] * i] = 1;
    
21.                         if (i % c[j] == 0) break;
    
22.                 }
    
23.         }
    
24. }
    
25. 
    
26. void solve(int i) {
    
27.         for (int j = 1; c[j] * c[j] <= i && j <= tot; ++j) {
    
28.                 while (i % c[j] == 0) {
    
29.                         ++frac[c[j]];
    
30.                         i /= c[j];
    
31.                         lastnum = max(lastnum, c[j]);
    
32.                 }
    
33.         }
    
34.         if (i > 1) {
    
35.                 ++frac[i];
    
36.                 lastnum = max(lastnum, i);
    
37.         }
    
38. }
    
39. 
    
40. int main() {
    
41.         scanf("%d%d", &n, &m);
    
42.         init();
    
43.         scanf("%d", &n);              //应该是scanf,不是scanf_s
    
44.         for (int i = m + 1; i <= n; ++i) {
    
45.                 solve(i);
    
46.         }
    
47.         for (int i = 1; i <= tot; ++i) {
    
48.                 if (frac[c[i]]) {
    
49.                         printf("%d", c[i]);
    
50.                         if (frac[c[i]] != 1) {
    
51.                                 printf("^%d", frac[c[i]]);
    
52.                         }
    
53.                         if (c[i] != lastnum) {
    
54.                                 printf("*");
    
55.                         } else {
    
56.                                 break;
    
57.                         }
    
58.                 }
    
59.         }
    
60.         return 0;
    
61. }

复制代码

zhangjinxuan

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

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

sfqxx

嘿嘿

jhq999

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

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

1. #include <stdio.h>
   
2. int num[3000001][2],pnum[3000001][2],plen=1;
   
3. int fun(int n)
   
4. {
   
5.     if(num[n][0])
   
6.     {
   
7.         fun(num[n][0]);
   
8.         fun(num[n][1]);
   
9.     }
   
10.     else
    
11.     {
    
12.         pnum[num[n][1]][1]+=1;
    
13.     }
    
14.     return 0;
    
15. }
    
16. int main ()
    
17. {
    
18.     int i=0,j,k=0,m,s=2;
    
19.     num[1][0]=1;
    
20.     num[1][1]=1;
    
21.     for(i=2,k=1;i<=3000000;i+=1)
    
22.     {
    
23.       if(0==num[i][0])
    
24.       {
    
25. 
    
26.           pnum[k][0]=i;
    
27.           num[i][1]=k;
    
28.           k+=1;
    
29.       }
    
30.         for(j=1;j<i&&pnum[j][0]*i<=3000000;j+=1)
    
31.         {
    
32.             m=pnum[j][0]*i;
    
33.             num[m][0]=i;
    
34.             num[m][1]=pnum[j][0];
    
35. 
    
36.             if(0==i%pnum[j][0])break;
    
37.         }
    
38.     }
    
39.     plen=k;
    
40.     for(i=3;i<=3000000;i+=1)fun(i);
    
41.     for(i=1;i<plen;i+=1)if(pnum[i][1])printf("%d^%d*",pnum[i][0],pnum[i][1]);
    
42.     return 0;
    
43. }
    

复制代码

sfqxx

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

WA

jhq999

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

1. #include <stdio.h>
   
2. int num[3000001][2],pnum[3000001][2],plen=1;
   
3. int fun(int n)
   
4. {
   
5.     if(num[n][0])
   
6.     {
   
7.         fun(num[n][0]);
   
8.         fun(num[n][1]);
   
9.     }
   
10.     else
    
11.     {
    
12.         pnum[num[n][1]][1]+=1;
    
13.     }
    
14.     return 0;
    
15. }
    
16. int main ()
    
17. {
    
18.     int i=0,j,k=0,n,m,s=2;
    
19.     num[1][0]=1;
    
20.     num[1][1]=1;
    
21.     for(i=2,k=1;i<=3000000;i+=1)
    
22.     {
    
23.       if(0==num[i][0])
    
24.       {
    
25. 
    
26.           pnum[k][0]=i;
    
27.           num[i][1]=k;
    
28.           k+=1;
    
29.       }
    
30.         for(j=1;j<i&&pnum[j][0]*i<=3000000;j+=1)
    
31.         {
    
32.             m=pnum[j][0]*i;
    
33.             num[m][0]=i;
    
34.             num[m][1]=pnum[j][0];
    
35. 
    
36.             if(0==i%pnum[j][0])break;
    
37.         }
    
38.     }
    
39.     plen=k;
    
40.     scanf("%d%d",&n,&m);
    
41.     for(i=m+1;i<=n;i+=1)fun(i);
    
42.     for(i=1,k=0;i<plen;i+=1)
    
43.     {
    
44.         if(pnum[i][1])
    
45.         {
    
46.             if(k)printf("*");
    
47.             k=1;
    
48.             if(pnum[i][1]>1)printf("%d^%d",pnum[i][0],pnum[i][1]);
    
49.             else printf("%d",pnum[i][0]);
    
50. 
    
51.         }
    
52.     }
    
53.     return 0;
    
54. }
    

复制代码

sfqxx

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

AC

jhq999

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