题解 P3708 【koishi的数学题】

本题是要求从1到n每一个整数的f函数值，且n较大，可以想到使用递推的方法。 现在让我们想一想，从f(x)到f(x+1)，f值有什么变化呢？ 如果不考虑取余，那么f(x+1)=f(x)+n。但是由于x+1%y可能为0，而我们在处理时却把它认为是y了，因此我们只要减去y，就可以得到正确的结果了。 那些数会成为这样的y呢？自然就是x+1所有的因数。因此我们只要用类似筛法的方法计算出每个数的y的和，就可以递推了。 程序中由于因数1和x+1不方便计算，在递推时做了处理。 另外，由于本题的输出较多，使用了输出优化。 代码如下： ```c #include <stdio.h> typedef unsigned long long ull; void out(ull); char tmp[30]; unsigned long f[1000001]={0}; //这么大的数组，必须作为全局变量，否则爆栈 //本程序中的f[x]指x的所有大于1且小于x的因数之和 int main(void){ int n,i,j,ndiv2; ull ans; scanf("%d",&n); ndiv2=(n>>1); for (i=2;i<=ndiv2;i++) for (j=(i<<1);j<=n;j+=i) //从2i开始,枚举2i, 3i, 4i, ... f[j]+=i; ans=n-1; //f(1)=n-1 out(ans); for (i=2;i<=n;i++){ ans=ans+n-1-f[i]-i; //f(x)=f(x-1)+n-所有的y之和 out(ans); } return 0; } void out(ull x){ int i=0; while (x){ tmp[i++]=(x%10)+'0'; x/=10; } for (i--;i>=0;i--) putchar(tmp[i]); putchar(' '); } ``` 另外说一句，这是我4月月赛R2 AC的唯一一题(而且交了3次)，还真的要提高知识水平啊！