【数论，找规律】Uva 11526

原来做过的题再看还是没想出来，看来当时必然没有真正理解。这次回顾感觉理解更透彻了。

网上的题解差不多都是一个版本，而且感觉有点扯。根据n=20猜出来的？

好吧哪能根据一个就猜到那么变态的公式。其实这题稍微找下规律就好。当然可能没有公式法效率高，但理解起来更容易吧。

你用n=20的例子，那么我也用。但我的想法是这样的。

sum = 0;

我们考虑 i 是多少时 n/i = 1: 20/1 = 20, 故i <= 20，又20/2 = 10, 故i > 10，即 10 < i <= 20 时，n/i = 1； sum += 1*(n/1 - n/2);

同理我们考虑 i 是多少时 n/i = 2: 20/2 = 10, 故i <= 10，又20/3 = 6, 故i > 6，即 6 < i <= 10 时，n/i = 2； sum += 2*(n/2 - n/3)；

继续我们考虑 i 是多少时 n/i = 3: 20/3 = 6, 故i <= 6，又20/4 = 5, 故i > 5，即 5 < i <= 6 时，n/i = 3； sum += 3*(n/3 - n/4)；

你们现在找到规律了吗?

需要注意的一点是，越往后n/i就不会按自然数增长了，所以在计算到 (n/i - n/(i+1)) == 1 时就需要退出这个求解的方式，转而按照正常计算方法计算 i+1 ~ n的 n/i值；

什么？会超时？事实证明不会哦，因为按之前的算法已经将 i 的范围缩小到logn了，所以之后的循环不会超时的~

/*

Problem: Uva 11526

Tips:    数论, 找规律

Date:    2015.7.27

*/

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<algorithm>

using namespace std;

typedef long long ull;

void solve(ull n)

{

    ull res = ;

    ull i = ;

    for(i = ; i <= n; i++)

    {

        res += i*(n/i - n/(i+));

        if(n/i - n/(i+) <= )

            break;

    }

    int st = n/(i+);

    for(int i = st; i >= ; i--)

        res += n/i;

    cout << res << endl;

}

int main()

{

    int T; cin >> T;

    while(T--)

    {

        ull n;  cin >> n;

        solve(n);

    }

    return ;

}

巴特西

【数论，找规律】Uva 11526 - H(n)

最新文章

热门文章