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

耀耀切克闹

#include<stdio.h>
int pow(int a,int b)
{
        int i=1;
        if(b==0) a=1;
        else for(i=1;i<=b;i++)
        a*=a;
        return(a);
}
int main()
{
        int m,n;
        while(scanf("%d %d",&n,&m)!=EOF)
        {
                int x=0,y=0,i=0,j=0,a[n];
                for(x=0;((pow(2,x))*(pow(3,y)))<n;x++)
                   for(y=0;((pow(2,x))*(pow(3,y)))<n;y++)
                          a[i++]=(pow(2,x))*(pow(3,y));
                printf("%d",i);
        }
        return 0;
}

设 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

#include <stdio.h>

long long int mypow(int a,int b)
{
    long long int t=1;
    if(b==0) 
        return 1;
    else
        for(int i=1;i<=b;i++) t*=a;
    return t;
}

int main()
{
    long long int m=10000000;
    int n=100;
    long long int result[10000]={0};
    int count=0;
    for(int i=0;1;i++)
    {
        for(int j=0;1;j++)
        {
            long long tmp=mypow(2,i)*mypow(3,j);
            if (tmp<=m)
            {
                result[count++]=tmp;
            }
            else
            {
                break;
            }
        }
        if (mypow(2,i)>m)
        {
            break;
        }
    }
    for (int i=0;i<count;i++)
    {
        for(int j=i+1;j<count;j++)
        {
            if (result[i]>result[j])
            {
                int s=result[i];
                result[i]=result[j];
                result[j]=s;
            }
        }
    }
    printf("共有%d个数据满足要求，其中排序后第100个数据是 %lld\n",count,result[99]);
    return 0;
}

/*
PS C:\Users\Administrator> ./ct
共有190个数据满足要求，其中排序后第100个数据是 93312
*/

跳转到最佳答案楼层

wp231957

#include <stdio.h>

long long int mypow(int a,int b)
{
    long long int t=1;
    if(b==0) 
        return 1;
    else
        for(int i=1;i<=b;i++) t*=a;
    return t;
}

int main()
{
    long long int m=10000000;
    int n=100;
    long long int result[10000]={0};
    int count=0;
    for(int i=0;1;i++)
    {
        for(int j=0;1;j++)
        {
            long long tmp=mypow(2,i)*mypow(3,j);
            if (tmp<=m)
            {
                result[count++]=tmp;
            }
            else
            {
                break;
            }
        }
        if (mypow(2,i)>m)
        {
            break;
        }
    }
    for (int i=0;i<count;i++)
    {
        for(int j=i+1;j<count;j++)
        {
            if (result[i]>result[j])
            {
                int s=result[i];
                result[i]=result[j];
                result[j]=s;
            }
        }
    }
    printf("共有%d个数据满足要求，其中排序后第100个数据是 %lld\n",count,result[99]);
    return 0;
}

/*
PS C:\Users\Administrator> ./ct
共有190个数据满足要求，其中排序后第100个数据是 93312
*/

wp231957

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

#include <stdio.h>

long long int mypow(int a,int b)
{
    long long int t=1;
    if(b==0)  return 1;
    for(int i=1;i<=b;i++) t*=a;
    return t;
}

int main()
{
    long long int m=10000000;
    int n=100;
    long long int result[10000]={0};
    int count=0;
    for(int i=0;mypow(2,i)<=m;i++)
    {
        for(int j=0;mypow(2,i)*mypow(3,j)<=m;j++)
        {
            result[count++]=mypow(2,i)*mypow(3,j);
        }
    }
    for (int i=0;i<count;i++)
    {
        for(int j=i+1;j<count;j++)
        {
            if (result[i]>result[j])
            {
                int s=result[i];
                result[i]=result[j];
                result[j]=s;
            }
        }
    }
    printf("共有%d个数据满足要求，其中排序后第100个数据是 %lld\n",count,result[99]);
    return 0;
}

/*
PS C:\Users\Administrator> ./ct
共有190个数据满足要求，其中排序后第100个数据是 93312
*/

jhq999

#include<stdio.h>
int pow(int a,int b)
{
        int i=1,s=1;
        if(b>0)
                        for(i=1;i<=b;i++)s*=a;
        return(s);
}
int main()
{
        int m,n; 
                
       scanf("%d %d",&n,&m);
       int x=0,y=2,i=0,j=0,s=1,flag=1;
           for(x=0;flag;x++)
           {
                   flag=0;
                   for(y=0;(s=pow(2,x)*pow(3,y))<n;y++)
                   {
                           flag=1;
                           i++;
                           if(i==m) printf("%d\n",s);
                   }
           }
       printf("%d",i);
        
                
        return 0;
}

wp231957

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

排序是咋绕过去的

耀耀切克闹

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

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

傻眼貓咪

#include <stdio.h>
#include <math.h>
#include <stdlib.h>

int f(int x, int y){
        return pow(2, x) * pow(3, y);
}

int compare(const void *a, const void *b){
   return *(int*)a - *(int*)b;
}

int main(){
        int
                n, m,
                count,
                a, b,
                N;
        
        scanf("%d%d", &n, &m);
        
        a = log2(n) + 1;
        b = log2(n) / log2(3) + 1;
        N = a*b;
        
        int arr[N];
        
        for(int i = 0; i < N; i++)
        arr[i] = n+1;

        for(int x = 0, i = 0; x < a; x++){
                for(int y = 0; y < b; y++){
                        if(f(x, y) < n && f(x, y) > 0){
                                arr[i++] = f(x, y);
                        }
                }
        }
        
        qsort(arr, N, sizeof(int), compare);
        
        for(int i = 0; arr[i] < n; i++){
                count = i + 1;
        }
        
        printf("%d\n\n%d", count, arr[m - 1]);
        return 0;
}

jhq999

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

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