[已解决]各位大佬帮忙看道幂积序列的题目

耀耀切克闹

1. #include<stdio.h>
   
2. int pow(int a,int b)
   
3. {
   
4.         int i=1;
   
5.         if(b==0) a=1;
   
6.         else for(i=1;i<=b;i++)
   
7.         a*=a;
   
8.         return(a);
   
9. }
   
10. int main()
    
11. {
    
12.         int m,n;
    
13.         while(scanf("%d %d",&n,&m)!=EOF)
    
14.         {
    
15.                 int x=0,y=0,i=0,j=0,a[n];
    
16.                 for(x=0;((pow(2,x))*(pow(3,y)))<n;x++)
    
17.                    for(y=0;((pow(2,x))*(pow(3,y)))<n;y++)
    
18.                           a[i++]=(pow(2,x))*(pow(3,y));
    
19.                 printf("%d",i);
    
20.         }
    
21.         return 0;
    
22. }

复制代码

设 x,y 为非负整数，试计算集合 M={(2^x)*(3^y),x>=0,y>=0} 的元素不大于指定整数 n 的个数，并求这些元素从小到大排序的第 m 项。

输入描述
多组输入，每组一行，输入 n 和 m，n 和 m 之间用一个空格分开

输出描述
对于每组输入，输出数列中不大于 n 的项数以及第 m 项的值，这两个数占两行。

样例输入：
10000000 100

样例输出：
190

93312

这道题我运行出来的结果很奇怪，但是我又不知道怎么改，查了网上的答案，是说要反过来思考，但是n很大的时候就运行不出来结果

最佳答案

月排行榜 / 总排行榜

wp231957

2022-4-21 09:13:28

1. #include <stdio.h>
   
2. 
   
3. long long int mypow(int a,int b)
   
4. {
   
5.     long long int t=1;
   
6.     if(b==0)
   
7.         return 1;
   
8.     else
   
9.         for(int i=1;i<=b;i++) t*=a;
   
10.     return t;
    
11. }
    
12. 
    
13. int main()
    
14. {
    
15.     long long int m=10000000;
    
16.     int n=100;
    
17.     long long int result[10000]={0};
    
18.     int count=0;
    
19.     for(int i=0;1;i++)
    
20.     {
    
21.         for(int j=0;1;j++)
    
22.         {
    
23.             long long tmp=mypow(2,i)*mypow(3,j);
    
24.             if (tmp<=m)
    
25.             {
    
26.                 result[count++]=tmp;
    
27.             }
    
28.             else
    
29.             {
    
30.                 break;
    
31.             }
    
32.         }
    
33.         if (mypow(2,i)>m)
    
34.         {
    
35.             break;
    
36.         }
    
37.     }
    
38.     for (int i=0;i<count;i++)
    
39.     {
    
40.         for(int j=i+1;j<count;j++)
    
41.         {
    
42.             if (result[i]>result[j])
    
43.             {
    
44.                 int s=result[i];
    
45.                 result[i]=result[j];
    
46.                 result[j]=s;
    
47.             }
    
48.         }
    
49.     }
    
50.     printf("共有%d个数据满足要求，其中排序后第100个数据是 %lld\n",count,result[99]);
    
51.     return 0;
    
52. }
    
53. 
    
54. /*
    
55. PS C:\Users\Administrator> ./ct
    
56. 共有190个数据满足要求，其中排序后第100个数据是 93312
    
57. */

复制代码

跳转到最佳答案楼层

wp231957

1. #include <stdio.h>
   
2. 
   
3. long long int mypow(int a,int b)
   
4. {
   
5.     long long int t=1;
   
6.     if(b==0)
   
7.         return 1;
   
8.     else
   
9.         for(int i=1;i<=b;i++) t*=a;
   
10.     return t;
    
11. }
    
12. 
    
13. int main()
    
14. {
    
15.     long long int m=10000000;
    
16.     int n=100;
    
17.     long long int result[10000]={0};
    
18.     int count=0;
    
19.     for(int i=0;1;i++)
    
20.     {
    
21.         for(int j=0;1;j++)
    
22.         {
    
23.             long long tmp=mypow(2,i)*mypow(3,j);
    
24.             if (tmp<=m)
    
25.             {
    
26.                 result[count++]=tmp;
    
27.             }
    
28.             else
    
29.             {
    
30.                 break;
    
31.             }
    
32.         }
    
33.         if (mypow(2,i)>m)
    
34.         {
    
35.             break;
    
36.         }
    
37.     }
    
38.     for (int i=0;i<count;i++)
    
39.     {
    
40.         for(int j=i+1;j<count;j++)
    
41.         {
    
42.             if (result[i]>result[j])
    
43.             {
    
44.                 int s=result[i];
    
45.                 result[i]=result[j];
    
46.                 result[j]=s;
    
47.             }
    
48.         }
    
49.     }
    
50.     printf("共有%d个数据满足要求，其中排序后第100个数据是 %lld\n",count,result[99]);
    
51.     return 0;
    
52. }
    
53. 
    
54. /*
    
55. PS C:\Users\Administrator> ./ct
    
56. 共有190个数据满足要求，其中排序后第100个数据是 93312
    
57. */

复制代码

wp231957

代码可以简化一下，但是我觉得排序好像绕不过去

1. #include <stdio.h>
   
2. 
   
3. long long int mypow(int a,int b)
   
4. {
   
5.     long long int t=1;
   
6.     if(b==0)  return 1;
   
7.     for(int i=1;i<=b;i++) t*=a;
   
8.     return t;
   
9. }
   
10. 
    
11. int main()
    
12. {
    
13.     long long int m=10000000;
    
14.     int n=100;
    
15.     long long int result[10000]={0};
    
16.     int count=0;
    
17.     for(int i=0;mypow(2,i)<=m;i++)
    
18.     {
    
19.         for(int j=0;mypow(2,i)*mypow(3,j)<=m;j++)
    
20.         {
    
21.             result[count++]=mypow(2,i)*mypow(3,j);
    
22.         }
    
23.     }
    
24.     for (int i=0;i<count;i++)
    
25.     {
    
26.         for(int j=i+1;j<count;j++)
    
27.         {
    
28.             if (result[i]>result[j])
    
29.             {
    
30.                 int s=result[i];
    
31.                 result[i]=result[j];
    
32.                 result[j]=s;
    
33.             }
    
34.         }
    
35.     }
    
36.     printf("共有%d个数据满足要求，其中排序后第100个数据是 %lld\n",count,result[99]);
    
37.     return 0;
    
38. }
    
39. 
    
40. /*
    
41. PS C:\Users\Administrator> ./ct
    
42. 共有190个数据满足要求，其中排序后第100个数据是 93312
    
43. */

复制代码

jhq999

1. #include<stdio.h>
   
2. int pow(int a,int b)
   
3. {
   
4.         int i=1,s=1;
   
5.         if(b>0)
   
6.                         for(i=1;i<=b;i++)s*=a;
   
7.         return(s);
   
8. }
   
9. int main()
   
10. {
    
11.         int m,n;
    
12.                
    
13.        scanf("%d %d",&n,&m);
    
14.        int x=0,y=2,i=0,j=0,s=1,flag=1;
    
15.            for(x=0;flag;x++)
    
16.            {
    
17.                    flag=0;
    
18.                    for(y=0;(s=pow(2,x)*pow(3,y))<n;y++)
    
19.                    {
    
20.                            flag=1;
    
21.                            i++;
    
22.                            if(i==m) printf("%d\n",s);
    
23.                    }
    
24.            }
    
25.        printf("%d",i);
    
26.        
    
27.                
    
28.         return 0;
    
29. }

复制代码

wp231957

jhq999 发表于 2022-4-21 09:43

排序是咋绕过去的

耀耀切克闹

wp231957 发表于 2022-4-21 09:46
排序是咋绕过去的

嗷嗷我想先把小于n的元素个数写出来的，但是结果不对嘛，排序还没写

傻眼貓咪

1. #include <stdio.h>
   
2. #include <math.h>
   
3. #include <stdlib.h>
   
4. 
   
5. int f(int x, int y){
   
6.         return pow(2, x) * pow(3, y);
   
7. }
   
8. 
   
9. int compare(const void *a, const void *b){
   
10.    return *(int*)a - *(int*)b;
    
11. }
    
12. 
    
13. int main(){
    
14.         int
    
15.                 n, m,
    
16.                 count,
    
17.                 a, b,
    
18.                 N;
    
19.        
    
20.         scanf("%d%d", &n, &m);
    
21.        
    
22.         a = log2(n) + 1;
    
23.         b = log2(n) / log2(3) + 1;
    
24.         N = a*b;
    
25.        
    
26.         int arr[N];
    
27.        
    
28.         for(int i = 0; i < N; i++)
    
29.         arr[i] = n+1;
    
30. 
    
31.         for(int x = 0, i = 0; x < a; x++){
    
32.                 for(int y = 0; y < b; y++){
    
33.                         if(f(x, y) < n && f(x, y) > 0){
    
34.                                 arr[i++] = f(x, y);
    
35.                         }
    
36.                 }
    
37.         }
    
38.        
    
39.         qsort(arr, N, sizeof(int), compare);
    
40.        
    
41.         for(int i = 0; arr[i] < n; i++){
    
42.                 count = i + 1;
    
43.         }
    
44.        
    
45.         printf("%d\n\n%d", count, arr[m - 1]);
    
46.         return 0;
    
47. }

复制代码

jhq999

wp231957 发表于 2022-4-21 09:46
排序是咋绕过去的

没想排序，只不过想测试下i==m时的值是否正确,估计是样例不具有普遍性
前面出来了，排序就简单了