| 网站首页 | 业界新闻 | 小组 | 交易 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
共有 1158 人关注过本帖
标题:求最小的有500个约数的三角形数
只看楼主 加入收藏
kirov_tujin
Rank: 2
等 级:论坛游民
帖 子:7
专家分:10
注 册:2013-3-16
结帖率:33.33%
  已结贴   问题点数:20  回复次数:5   
求最小的有500个约数的三角形数
原题来自Project Euler http://
Highly divisible triangular number


Problem 12
 

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:
 
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
 
Let us list the factors of the first seven triangle numbers:
 
 1: 1
  3: 1,3
  6: 1,2,3,6
 10: 1,2,5,10
 15: 1,3,5,15
 21: 1,3,7,21
 28: 1,2,4,7,14,28
 
We can see that 28 is the first triangle number to have over five divisors.
 
What is the value of the first triangle number to have over five hundred divisors?

我注意到三角形数的通项公式是(n+1)n/2,因此试图根据(n+1)、n的约数个数求出对应三角形数的约数个数,但是算法似乎有点问题,求指教。
我的思路是,n和n+1互质,因此他们各自的约数、约数的积都应该是乘积的约数。但是这样可能会有重复计算的问题。
还是说就应该暴力一点直接算?但数字又好像很大,可能会数据溢出……
#include <iostream>

using namespace std;

int main()
{
    int n, i, dvsr;
    int c1[3] = { 0, 0}, c2[3] = { 0, 0};
    long int numb, count, numb1, count1;

    const long int N = 1000000;

    numb = 0;
    count = 0;

    for(n = 1;;n ++)
    {
        c2[0] =
        c2[1] = 0;

        for(i = 1;i <= n;i ++)
        {
            if(!(n%i))
            {
                c2[0] ++;               //stands for the number of devisers
                if(i%2)c2[1] ++;        //stands for odd devisors
            }
        }

        dvsr = c2[0]+c1[0]-1            //the sum of devisors
                +c2[0]*c1[0]-3          //the product of devisors
                -c2[1]-c1[1];
        numb += n;
        if(numb >= N)
        {
            count += N;
            numb -= N;
        }

        if(dvsr >= 500)break;

        c1[0] = c2[0];
        c1[1] = c2[1];
    }

    numb1 = count1 = 0;                //to check if the numb is correct
    for(i = 0;i <= n;i ++)
    {
        numb1 += i;
        if(numb1 > N)
        {
            numb1 -= N;
            count1 ++;
        }
    }

    cout << "Hello world!" << endl
        << n << endl << count << endl << numb << endl << dvsr << endl
        << numb1 << endl << count1 << endl;
    return 0;
}

搜索更多相关主题的帖子: generated generated sequence sequence triangle triangle 
2013-03-20 10:47
kirov_tujin
Rank: 2
等 级:论坛游民
帖 子:7
专家分:10
注 册:2013-3-16
  得分:0 
原来是我想多了……暴力法就可以了……不过还是想问问原来的思路可以吗?
2013-03-20 11:25
azzbcc
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:江西财经大学
等 级:贵宾
威 望:81
帖 子:3293
专家分:12919
注 册:2012-11-4
  得分:10 
可以的,而且你所说的 可能的重复 是不存在的


[fly]存在即是合理[/fly]
2013-03-20 13:09
azzbcc
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:江西财经大学
等 级:贵宾
威 望:81
帖 子:3293
专家分:12919
注 册:2012-11-4
  得分:0 
刚写了一个求因数个数的,质因数分解是个不错的思路、、、


[fly]存在即是合理[/fly]
2013-03-20 17:41
azzbcc
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:江西财经大学
等 级:贵宾
威 望:81
帖 子:3293
专家分:12919
注 册:2012-11-4
  得分:0 
突然想到这个数肯定超过 1亿了,还得考虑高精度吧


[fly]存在即是合理[/fly]
2013-03-20 17:49
tompobing
Rank: 8Rank: 8
等 级:蝙蝠侠
帖 子:260
专家分:809
注 册:2012-12-9
  得分:10 
我也在想这道题,来看看
2013-03-26 21:54
快速回复:求最小的有500个约数的三角形数
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.063232 second(s), 8 queries.
Copyright©2004-2020, BCCN.NET, All Rights Reserved