前面三题,就B题一道900的题目让我wa了两发,而且有点难看出来
主要是想不到。。不知道该怎么像。
应该算是题目理解不清晰吧,很麻烦。。这个原因可以说是没有一个完整的思考路径,我能够直接想到答案接近的处理方法,但是细节上没有注意。在考虑问题的时候可能。。需要慢一些,太快了,容易漏下点东西,然后就会一直wa。
A和C都是水题(其实E也差不多,只要会tarjan的人都能写)
这个D题,很值得讨论一下,是一个复盘的很好的对象。
我先把我考试的时候的思路写下来
首先,我们可以知道,对于a数组里面的两个数字\(a[i],a[j]\ (i\leq j)\),对答案的贡献是\(gcd(a[i],a[j])*(n-j)\),这是可以计算得到的。
但是,不管怎么样,只要我们试图去计算两个数字之间的\(gcd\),这个代码就必然超时。因为,很明显,\(gcd(a[i],a[j])\)和\(gcd(a[j],a[k])\)是没有任何明显的数值上的关系的,也就是,在这个层面上,我们尝试去计算两个数字之间的gcd并且统计,是绝对打不破\(O(n^2)\)复杂度的瓶颈的。而\(n=1e5\),这是不能接受的。
所以要转换思路,假如\(gcd(a[i],a[j])\)换成其他计算,这题可能就假了,gcd是有它本身的特殊性的,我们其实是能从上面的分析得到的(不然就是假题)。
所以我们要做的就是利用gcd的特殊性来进行统计答案。gcd是最大公约数,这是他的定义。我们可以发现,最大公约数的大小和参与计算的数值是有直接关系的,而\(a[i]\leq 1e5\),这就能说明很多了。
然后我考试的时候就开始脑抽了。。我算了算\(1e5\)范围的质数(?我在干什么),发现只有少于1e4个,然后觉得可做,然后想了想发现gcd和质数没什么关系,然后就觉得这题做不了了。。。
其实这题目和质数就是没有任何关系的。有关系的是每一个数字的因数。我们可以先对a数组排序,然后从小到大枚举\(a[i]\),然后再枚举\(a[i]\)的因数,对于它的每一个因数,统计前面有多少个数字出现了这个因数,给答案先加上。
这很明显的是有重复的,但是我们在\(O(n\sqrt{a[i]})\)的复杂度内统计到了一个类似答案的东西!
然后后面的事情其实就是减去重复的部分了,重复的部分就是类似一个数字有因子2,4,8,而另一个数字也有,那这三个因数就都会被统计一次。我们要做的,就是枚举每一个因数,然后枚举它的每一个倍数,让小的因数的数量减去属于它的大的因数的数量,因为它不是gcd,它只是一个公约数,并不是最大的。
这个容斥的过程是很难想的。
其实也还好。
就是,sum[i]先表示有几个数字以i作为公约数,然后对于sum[2],很明显,sum[4]肯定是在sum[2]里面被统计过的,sum[6]也是,sum[8]也是,sum........,那我们用sum[2]-=sum[4]+sum[6]+sum[8],一直减到最后,剩下的sum[2]的内容,不就是以2作为最大公约数的数字数量了吗?因为如果两个数字没有2这个公约数,它开始就不在,如果他们有其他的更大的公约数,那它就是2的倍数,刚刚的过程就已经把它剪掉了。
剩下的,不就是答案了?
这个过程是\(O(a[i]\sqrt{a[i]})\)的,所以这个算法的总体的时间复杂度就是\(O((n+a[i])\sqrt{a[i]})\)
可以通过。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline ll read() {
char c=getchar();ll a=0,b=1;
for(;c<'0'||c>'9';c=getchar())if(c=='-')b=-1;
for(;c>='0'&&c<='9';c=getchar())a=a*10+c-48;return a*b;
}
ll n,a[200101];
ll sum[200101],cnt[200101];//sum[i]表示有几个数字以i作为公约数,后面处理之后就变成了作为最大公约数了
vector<ll> fact[100201];
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
for(int i=1;i<=100000;i++)
{
for(int j=i;j<=100000;j+=i)
{
fact[j].push_back(i);//以j的因子有那些
}
}
int T=read();
while(T--)
{
n=read();
memset(sum,0,sizeof(sum));
memset(cnt,0,sizeof(cnt));
for(int i=1;i<=n;i++)
{
a[i]=read();
}
sort(a+1,a+1+n);
for(int i=1;i<=n;i++)
{
int len=fact[a[i]].size();
for(int j=0;j<len;j++)
{
sum[fact[a[i]][j]]+=cnt[fact[a[i]][j]]*(n-i);
cnt[fact[a[i]][j]]++;//前面有几个数字
}
}
ll ans=0;
for(int i=a[n];i>=1;i--)
{
for(int j=i+i;j<=100000;j+=i)
{
sum[i]-=sum[j];
}
ans+=sum[i]*i;
}
cout<<ans<<endl;
}
return 0;
}
为什么我会想不到这个过程?
(不得不承认我都不知道为什么我会tm想到质数。。)
这可以算是gcd的偏难的题目了,把dp和gcd结合了。
这个先统计,然后再减去重复的想法,本身就是比较难想的。它是很缺少启发性的,因为在你统计的时候,你要怎么才能知道你统计的东西是能够这种去重得到的呢?
呃,对于这一题其实还好,因为你知道了所有的因数之后,gcd其实是一个类似他们的导数的东西,它只是相邻两个之间的增量吧。
还是有点可能能够直接看出来的。
但是对于其他这种题呢?
那估计就是难题了。这个时候我感觉刷题量的优势就体现出来了。刷的题多了,其实就知道了这样去处理gcd是可以的。或者说,其实就知道了gcd的处理方式比较唯一或者说是不多。那就很快了。因为除了这个办法没有其他办法。
对于这题的复盘,主要就是记录一下这个先统计再去重的思路可以用再这种题目上,这样以后遇到这种题目就能写出来了。还有因数的处理吧。
还是要多写,多看,多想啊。
标签:gcd,sum,vp,因数,就是,Div,911,统计,数字 From: https://www.cnblogs.com/HLZZPawa/p/18047910