洛谷:P2926 [USACO08DEC]Patting Heads S（数学。普及/提高-）

题目：

代码：我是用之前的数组前递和排序，替换：map和set：竟然超时了。

#include<bits/stdc++.h>
using namespace std;
int A1[100001],A2[100001];
int D[1000005];
int cnt[1000005];
int main()
{
 int n;
 cin>>n;
 memset(D,0,sizeof(D));
 memset(cnt,0,sizeof(cnt));
 for(int i=0;i<n;i++)
 {
  cin>>A1[i];
  A2[i]=A1[i];
  cnt[A1[i]]++;
 }
 sort(A1,A1+n);
 int last=A1[0];
 int n2=1;
 for(int i=1;i<n;i++)
 {
  if(A1[i]==last) continue;
  A1[n2]=A1[i];
  n2++;
  last=A1[i];
 }
 for(int i=0;i<n2;i++)
 {
  for(int j=i+1;j<n2;j++)
  {
   if(A1[j]%A1[i]==0)
   {
    D[A1[j]]+=cnt[A1[i]];
   }   
  }
 }
 for(int i=0;i<n;i++)
 {
  cout<<D[A2[i]]+cnt[A2[i]]-1<<endl;
 }
}

题解：

也是很简单的思路啊！

还可以优化点是：相同数的因子重复算了，用记忆化存储就欧克啦！

还有一点，人家是到根号，而非除以2，因为每个因子都有与其对应的因子。

反思自己的为什么没有过去呢？

自己的相当于找x的因子，可能1到x都找了，这里没有优化，所以超时了。