Bzoj 1968: [Ahoi2005]COMMON 约数研究

1968: [Ahoi2005]COMMON 约数研究 Time Limit: 1 Sec Memory Limit: 64 MB Description Input 只有一行一个整数 N（0 < N < 1000000）。 Output 只有一行输出，为整数M，即f(1)到f(N)的累加和。 Sample Input 3 Sample Output 5 HINT Source Day2

/* 省选傻逼题. 这题数据线性递推就能过. 恩就是这样 for(int i=1;i<=n;i++) ans+=n/i. 找1-n中i的倍数的个数. 然后用等差数列加速就变成了下边这个样子. 复杂度sqrt(n). */ #include<iostream> #define LL long long using namespace std; int ans,x,y,tot=0; void slove(int n) { int i=1,j; while(i<=n) { j=n/(n/i); tot+=n/i*(j-i+1); i=j+1; } return ; } int main() { cin>>x; slove(x); cout<<tot; return 0; }