[BZOJ 1968]约数研究

danihao123 posted @ 2016年2月15日 17:57 in 题解 with tags 数学 bzoj AHOI 省选 , 820 阅读

转载请注明出处：http://danihao123.is-programmer.com/

妙，妙啊！

此乃数学之大道也

直接递推+求约数会炸，但是……

你可以枚举约数x，然后求出区间内约数有它的个数，很明显是\( \lfloor n \div x \rfloor \)，然后求和就行了……

代码：

/**************************************************************
    Problem: 1968
    User: danihao123
    Language: C++
    Result: Accepted
    Time:32 ms
    Memory:1272 kb
****************************************************************/
 
#include <iostream>
using namespace std;
int main(){
    register int i;
    register unsigned long long ans=0;
    int n;
    cin>>n;
    for(i=1;i<=n;i++)
        ans+=n/i;
    cout<<ans<<endl;
    return 0;
}