题解 P3708 【koishi的数学题】

· · 题解

思路

老师上课讲的例题，方法真的很神奇。

观察样例，如果没有发现什么的话，就模拟打出一张表好了：(横坐标为x, 纵坐标为y)

显然每一横行加起来就是答案，神奇的是在于纵行！（不要问我怎么发现的）。

每一纵行的意义即是，对于一个固定的i, x递增时的x ~mod ~ i。可以发现它是以i个为循环的数列。

处理上面一个数列复杂度较高，但是我们可以这样处理：发现对于一个固定的i, x递增时的 x-（x mod i），它便是每i项增加i的一个数列。于是我们可以每i个数打一个标记，标记意为增加i。

然后我们可以发现，f(x)可以从f(x-1)推到，便是f(x-1)+n-1-标记。（类似于前缀和+差分维护吧）

代码

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
long long n,j,temp,ans,tag[MAXN]; //tag数组即为标记

int main(){
  scanf("%lld",&n);
  for(int i=2; i<=n; i++)
      for(int j=i; j<=n; j+=i)
          tag[j]+=i;  //处理tag数组,每i位加i
  for(int i=1; i<=n; i++)
  {
      ans+=n-tag[i]-1;
      printf("%lld ",ans); //递推得出答案
  }
  return 0;
}