#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<string>
#include<map>
#include<cstring>
#include<vector>
#define inf 1e9
#define ll long long
#define For(i,j,k) for(ll i=j;i<=k;i++)
#define Dow(i,j,k) for(ll i=k;i>=j;i--)
using namespace std;
ll ans1,ans2;
int main()
{
    ll n;
    while(1)
    {
        scanf("%d",&n);
        if(n==0)    break;
        ans1=0,ans2=0;
        ll tot=0;
        For(i,1,sqrt(n)-1)
        {
            ll t=n/i-n/(i+1);

            tot+=t;
            ans1+=(i*(t-1)+2*(n%i))*t/2;
            ans2+=i*t; 
        }
        For(i,1,n-tot)
            ans1+=n%i,ans2+=n/i;
        printf("%lld %lld\n",ans2,ans1);
    }
}

题解+代码

先说MOD：

打个表可以发现规律，也就是n div i相同的构成等差数列（其实根据定义显然）。所以i=1 到sqrt(n)，用公式求出n div j=i相同的数的余数和。然后再从I=1~sqrt(n)，把n mod i加进去即可。

DIV类似。

orz...

难度为4~

不过还是很值得一做的~

很有意思~

写完这题才知道什么叫执着，测评记录里连续1页半都时我交的，通过率下降了2个百分点。

把时间复杂度降到O（sqrt（n））加上一点优化。 找个几个小数据看下就知道了：

1 2 3 4 5 6 7 8 9 10 11

11 5 3 2 2 1 1 1 1 1 1

0 1 2 3 1 5 4 3 2 1 0

n div x =1 的是从 n div (1+1) ~ n div (1) 这一部分的余数为一个等差数列，公差为 1；

n div x =2 的是从 n div (2+1) ~ n div (2) 这一部分的余数为一个等差数列，公差为 2；

…… ……

n div x= sqrt(n)的是……………………

前面一部分直接累加上去

优化： 在计算的时候经常用到两个数 n/i 和 n / (i+1) ， 用变量存起来，避免重复计算， 除法太慢。

怎样读入啊

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 494ms

├ 测试数据 10：答案正确... 1681ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：2175ms

ORZ。。。。。。。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 291ms

├ 测试数据 10：答案正确... 1009ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1300ms

时间用的比较多，但总算过了，我推了好长一段时间。汗！

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 56ms

├ 测试数据 10：答案正确... 400ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：456ms

一定要预处理，否则必超，我因为没预处理n/(i+1)而提交了十几次

while(n!=0)

{

//预处理数组：

for(i=1;i

Orz voyagec2 !

顶LX

的确水题.

难度改低一点吧

水题...

我唯一的教训是当

m:=a[i]*a[j]-n

(a[i]*a[j]>longint,但是最后结果在Longint范围）的时候

请把a数组开成int64.

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：鸢刚?.. 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 212ms

├ 测试数据 10：答案正确... 791ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1003ms

AC但不知数据2是？

倒着考虑，你会发现规律

程序不到40行

原来要开 int64 呀 ...

总算AC了。常数优化太微缩了。

qword、int64的div奇慢，处理方法如下：

在算之前先预处理一个数组：a[k]=n div k (1

带狗.- -||

我恨你..

问你居然不告诉我..害我自己推了一个小时.- -!`

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 650ms

├ 测试数据 10：运行超时...

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：81 有效耗时：650ms

没啥好说 的

等 那个 puppy 现身。。。

那个 规律 不好找 啊

找到了 也不好写 啊

调了整整 一个 上午。。。

终于 跳出来 了

就差 Puppy 了。。

哈哈。。

终于过了。。。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 494ms

├ 测试数据 10：答案正确... 1166ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1660ms

用 qword 时

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 431ms

├ 测试数据 10：答案正确... 1494ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1925ms

用 int64 时

综上 用 qword　比较　实在

哈哈

一定要先想清楚再写,23行

膜拜楼下