C - A New Function (整除分块 + 玄学优化)

题目链接:https://cn.vjudge.net/contest/270608#problem/C

AC代码:

#include<cmath>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

# define ll long long

# define inf 0x3f3f3f3f

const int maxn = 100000+100;

int main()

{

    int T;

    cin>>T;

    int Case=0;

    while(T--)

    {

        ll n;

        cin>>n;

        ll ans=sqrt(n);

        ll sum=0;

        ll nex,pos=n/2;//出现两次的数的终点

        for(int i=2; i<=ans; i++)

        {

            nex=n/(i+1);//当i为2是,nex是出现两次的起点

            sum+=(i-1)*(pos-(nex+1)+1)*(pos+nex+1)/2;//用等差数列求和的公式.

            pos=nex;

        }

        for(int i=2; i<=pos; i++)

        {

            sum+=(n/i-1)*i;

        }

        cout<<"Case "<<++Case<<": "<<sum<<endl;

    }

    return 0;

}