首页 > 代码库 > lightoj 1089

lightoj 1089

很有意思的题目,1到n的所有数的约数的合。

sqrt(n)一次算两两边的。

    #include <cstdio>    #include <cstring>    #include <vector>    #include <cmath>    #include <stack>    #include <cstdlib>    #include <queue>    #include <map>    #include <iostream>    #include <algorithm>    #include <bits/stdc++.h>         using namespace std;    typedef long long LL;    LL cal(LL x)    {        LL ans=0;        for (LL i=2;i<=sqrt(x);i++)        {            ans+=(x/i-1)*i;            LL zuo=x/(i+1),you=x/(i);            if (you!=i)            {                ans+=(zuo+1+you)*(you-zuo)/2*(i-1);            }        }        return ans;    }         //long long getAns(long long m)    //{    //    long long ans = 0;    //    for(long long i = 2;i<=sqrt(m);i++)    //    {    //    ////前sqrt(n)个约数    //        ans += (m/i-1)*i;    //    ////约数个数为前sqrt(n)    //        long long j = m/i;    //        long long q = (m/(i+1));    //        if(j!=i)    //        {    //            ans += (j+q+1)*(j-q)/2*(i-1);    //        }    //    }    //    return ans;    //}         int main()    {        int T,ncas=1;        LL x;        scanf ("%d",&T);        while (T--)        {            scanf ("%lld",&x);            printf ("Case %d: %lld\n",ncas++,cal(x));        }        return 0;    }          

 

lightoj 1089