计算智能--龙龙

朱雀 2023-07-24 02:00 64阅读 0赞

## 题目描述 ##

1 龙龙  
Time Limit:1000MS Memory Limit:1000K  
题型: 编程题 语言: 无限制  
描述  
在比赛的时候，1Y(1 次AC)是很值得高兴的事情。但很多大牛总会因为很弱智的错误先WA 一次，再AC。  
而很多时候，这点罚时的差距使得他们与金牌无缘。弱智错误系列中最显著的就是忘记加龙龙。

龙龙外国人叫它作long long，表示64位整数，输入与输出64位整数则可以使用例如  
scanf("%lld", &a)与printf("%lld", a)的形式完成。很多图论和动态规划的题目中，  
虽然题目说最后输出的答案是32 位的整数，但中间计算的过程有时会超过int，这时我们就要使用龙龙了。

可惜的是，很多同学刚开始学写程序都是用VC的，在VC上是无法使用long long的，我们要用\_\_int64  
代替，输入与输出64位整数则可以使用例如scanf("%I64d", &a)与printf("%I64d", a)的形式完成。

但是提交上OJ 的时候，如果使用GCC或G++，都只支持long long，我们在提交时又得按照上边的改回来（的确挺麻烦,窘）。  
为了让知道龙龙的同学们记得使用龙龙，不知道的学习使用龙龙，下边有个很简单的函数，希望大家  
求出它的返回值：

long long H(int n)\{  
long long res = 0;  
int i;  
for(i = 1; i <= n; i=i+1 )\{  
res = (res + n/i);  
\}  
return res;  
\}

不过直接使用这个函数是会超时的，必须改造这个函数，当然这一定难不到未来的编程高手–你

输入格式  
第一行是数字T(T<=1021)表示case数，接下来T 行，每行一个整数n，n是一个32 位整数（保证可以由int 表示）。  
输出格式  
函数返回值。  
输入样例  
2  
5  
10  
输出样例  
10  
27  
提示  
作者 admin

## 这题的解法 ##

这道题目无脑暴力，题目说了是会超时的。所以这题我们不能无脑暴力，必须优化暴力过程。那么怎么优化呢？  
通过列举题目所给样例，可以发现，枚举过程中到了一定程度的时候会有很多值相同的枚举情况，这种情况是可以优化的。

首先：我们假设Q=sqrt(n)，当我们枚举n对应的这种情况时，我们先枚举i<=Q的情况，这种情况就直接枚举数量，用ans记录累加的数值。  
然后再枚举i>Q的情况，那么这种情况怎么枚举才能使得程序得到优化呢？首先我们设，X=n/Q;我们知道n/(n/(Q-1))-n/(n/Q)是两个数之间的个数差。那么(n/(n/(Q-1))-n/(n/Q))\*n/Q就是这之间的值的总和，我们只需要枚举1-X范围内的情况即可，每次都调用上述公式求解。

代码如下：

#include<stdio.h>
    #include<math.h>
    #define ll long long
    long long func(int n)
    {
        
        long long ans=0;
        if(n<1) return 0;
        int q=sqrt(n);
        for(int i=1;i<=q;i++)
            ans+=n/i;
            q=n/q;
        int temp=n/q;
            q--;
        for(;q>0;q--)
        {
        
            ans+=(n/q-temp)*q;
            temp=n/q;
        }
        return ans;
    }
    
    int main()
    {
        
        int a;
        int n;
        scanf("%d", &n);
        while(n--)
        {
        
            scanf("%d", &a);
            printf("%lld\n", func(a));
        }
    }