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 longusing 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;}新闻热点
疑难解答