数论
原谅我这么傻逼的题都不会做……
或许写成数学公式的形式比较容易想到解法?
$$ans=\sum_{i=1}^n \sum_{d|i} 1$$
……是不是感觉很水呀……是吧……改成先枚举d再枚举 i 看看……
$$ans=\sum_{d=1}^n \sum_{d|i} 1=\sum_{d=1}^n \lfloor\frac{n}{d}\rfloor$$
果然我是个傻逼……
/**************************************************************
Problem: 1968
User: Tunix
Language: C++
Result: Accepted
Time:32 ms
Memory:804 kb
****************************************************************/ #include<cstdio>
int main(){
int n,ans=;
scanf("%d",&n);
for(int i=;i<=n;i++) ans=ans+n/i;
printf("%d\n",ans);
return ;
}
1968: [Ahoi2005]COMMON 约数研究
Time Limit: 1 Sec Memory Limit: 64 MB
Submit: 1174 Solved: 884
[Submit][Status][Discuss]
Description
Input
只有一行一个整数 N(0 < N < 1000000)。
Output
只有一行输出,为整数M,即f(1)到f(N)的累加和。
Sample Input
3
Sample Output
5