算法优化 - 具有n个divisiors的最小数字

Question

这个问题是一个编程版第12题从projecteuler.net ..

通过添加自然数来生成三角数的序列.所以第7个三角形数字是1 + 2 + 3 + 4 + 5 + 6 + 7 = 28.前十个学期将是:

1,3,6,10,15,21,28,36,45,55,...

28号三角形将具有以下因素

28 = 1,2,4,7,28

我们可以看到28是第一个有超过五个除数的三角形数.

超过N个除数的第一个三角形数的值是多少？

(1 <= N <= 1000)

我编写的代码适用于N = 750.但是N = 1000需要很长时间.

#include <iostream>
#include <stdio.h>
#include <vector>

#define LL long long

using namespace std;

int main()
{
    int test;
    scanf("%d",&test);
    int v[10001]={0};
    int tnum=1,num=1;

    while(1)
    {
        int c=0;
        for(int i=1;i*i<=tnum;++i)
        {
            if(tnum%i==0)
            {
                ++c;
                if(i!=(tnum/i))
                {                       
                    ++c;
                }               
            }
        }
        if(v[c]==0)
            v[c]=tnum;

        //  cout << "c = "<<c<<" tnum = " << tnum << endl;
        if(c>1000)
        {
            break;
        }
        ++num;

        tnum += num; 
    }

    while(test--)
    {
        int n;
        scanf("%d",&n);
        ++n;
        while(v[n]==0)
        {
            ++n;
        }
        printf("%d\n",v[n]); 
    }

    return 0;
}

任何帮助或建议将不胜感激.谢谢.

编辑1 =回答这个问题 - 因为我们必须找到具有超过n个divisiors的下一个三角形数字,我们可以强制所有三角形数字并找到它们的divisiors数量.然后我们将看到更大的n值(n> 240)的模式

Answer 1

如果我告诉你938,839有多少除数,938,840有多少除数,你怎么用我给你的信息找出938,839*938,840的除数？

你怎么能用这个想法让你的算法运行速度快100倍？