企业官网建设流程全解析

题意分析

长度为n的序列a[i],求将序列划分为最少数列的区间，这些区间的要求是区间内任意选出任意数的乘积不等于x。

求解思路

要让区间数列尽可能少，就得尽可能的多向右扩展，能加入当前区间就加，加不了再开新区间。
↓
问题转为：新加入一个数y，这个区间的任意数的乘积是否会变成x。
↓
对于y而言，y*sum=x，sum是要判断的区间内任意数的乘积，我们发现

1. 只有y是x的约数，才能在乘以另一个数的时候变成x。也就是说，y如果不是x的约数，那么直接放进当前区间即可，不需要再作其他操作。
2. 当y是x的约数时，就要看这个区间内是否有可能构成x的乘积存在了，这里如何判断呢？感觉是一个难点。

解决：把所有的约数记录下来，来一个a[i]，就与这一段区间内的数相乘，如果结果是x的约数，就把它记录下来，方便后面用，如果相乘的结果不是x的约数，那么直接不用管。

代码实现

#include<bits/stdc++.h>usingnamespacestd;inta[100009],ans;unordered_set<int>s,cur;intmain(){intT;cin>>T;while(T--){s.clear();cur.clear();intn,x;ans=1;cin>>n>>x;for(inti=1;i<=n;i++)cin>>a[i];for(inti=1;i<=n;i++){if(x%a[i]!=0)continue;for(autoj:s)//计算当前段中所有数*a[i]{intk=a[i]*j;if(x%k==0){if(k==x){ans++;s.clear();cur.clear();break;}cur.insert(k);}}for(autoj:cur){s.insert(j);}cur.clear();if(x%a[i]==0)s.insert(a[i]);}cout<<ans<<endl;}}

样例过了，但没有在cf测，突然上不了cf了，后面再测把，先发出来。