1968: [Ahoi2005]COMMON 约数研究-白红宇

1968: [Ahoi2005]COMMON 约数研究

阅读量：7236 次

发布时间：2019-06-29

本文共 903 字，大约阅读时间需要 3 分钟。

1968: [Ahoi2005]COMMON 约数研究

Time Limit: 1 Sec Memory Limit: 64 MB

Submit: 1127 Solved: 852

[][][]

Description

Input

只有一行一个整数 N（0 < N < 1000000）。

Output

只有一行输出，为整数M，即f(1)到f(N)的累加和。

Sample Input

Sample Output

HINT

Source

题解：一个神题（HansBug：其实一开始看到别人的AC代码一个个才几百B有点被吓到了），其实我们可以逆向思维想这个问题，不要老想着小学学奥数时候学会的数字的约数个数公式，那样子只会添乱，只需要考虑各种不同的约数对于答案的贡献程度即可，即[N/I]（设约数为I），然后没了，可以当作水题了= =

1 /************************************************************** 2     Problem: 1968 3     User: HansBug 4     Language: Pascal 5     Result: Accepted 6     Time:88 ms 7     Memory:220 kb 8 ****************************************************************/ 9  10 var n,m,ans:int64;11 begin12      readln(n);m:=n;ans:=0;13      while m>0 do14            begin15                 inc(ans,n div m);16                 dec(m);17            end;18      writeln(ans);19      readln;20 end.

转载于:https://www.cnblogs.com/HansBug/p/4472039.html

你可能感兴趣的文章