题解：P10916 椰子

· · 题解

思路

由于每一个只有一个数的区间，其最大公约数都是这个区间本身。
所以我们不难得出，不管你把哪一个数变成 1 不同的公约数数量至少为 n-1。

那什么时候将一个数改成 1 后的答案为 n 呢。当有一些数的最大公因数为被改成 1 的那个数时，且这些数中没有与这个公因数相等的数。此时答案为 n。

不过显然预处理一遍所有情况的最大公因数会超时。

所以我在这里告诉大家一个取巧的方法 （赌样例不够完善）。其实这也是 IOI 赛制中的合理技巧。

那就是对于每个点只枚举长度最多为 10 的区间并记录这个区间的最大公因数。

为什么这样可以呢？因为我认为 10 个数约出的数小之又小，大概率其他区间的数依然可以约出来。而且一些数，两三个数约不出来，一堆数就更约不出来了。

于是我这份抽象的代码就对了。

代码展示

注意：用数组记录并清空数组会大大增加用时。

#include<bits/stdc++.h>
using namespace std;
const int N=5*1e5+10;
int n,a[N],t[N],ff[N];

unordered_map<int,bool>m;

int gcd(int a, int b) 
{
  while (b != 0) 
  {
    int tmp = a;
    a = b;
    b = tmp % b;
  }
  return a;
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<n;i++)
    {
        m.clear(); 
        int g=a[i]; m[a[i]]=1;
        for(int j=i+1;j<=min(i+10,n);j++)
        {
            m[a[j]]=1;

            g=gcd(a[j],g);

            if(g==1) break;

            if(m[g]) continue;
            else t[g]=1;
        }
    }
    cout<<n;
    for(int i=2;i<=n;i++)
    {
        cout<<' '<<n-1+t[i];
    }


}