[BZOJ 1968]约数研究

danihao123 posted @ 2016年2月15日 17:57 in 题解 with tags 数学 bzoj AHOI 省选 , 686 阅读
转载请注明出处: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;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter