海淀企业型网站建设,韩国手做配件网站,怎样在网站上做专栏,企业网站的网页设计题目大意
有一个长度为 n n n的序列 a a a#xff0c;你每次可以选择 gcd \gcd gcd不为一的两个数 a i a_i ai和 a i 1 a_{i1} ai1#xff0c;将两个数合并#xff0c;其值为两个数的 lcm \text{lcm} lcm#xff0c;也就是删去 a i 1 a_{i1} ai1#xff0c;再…题目大意
有一个长度为 n n n的序列 a a a你每次可以选择 gcd \gcd gcd不为一的两个数 a i a_i ai和 a i 1 a_{i1} ai1将两个数合并其值为两个数的 lcm \text{lcm} lcm也就是删去 a i 1 a_{i1} ai1再让 a i lcm ( a i , a i 1 ) a_i\text{lcm}(a_i,a_{i1}) ailcm(ai,ai1)。
求是否可以进行若干次操作使得序列 a a a的长度变为 1 1 1。如果可行就输出 Y e s Yes Yes否则输出 N o No No。 1 ≤ n ≤ 1 0 5 , 1 ≤ a i ≤ 700 1\leq n\leq 10^5,1\leq a_i\leq 700 1≤n≤105,1≤ai≤700 题解
首先我们要知道能合并的就合并并不存在合并一个会使其他原本能合并的变得不能合并。我们可以维护一个栈枚举每个元素将当前元素与栈顶元素求 gcd \gcd gcd如果 gcd \gcd gcd不为 1 1 1就取出栈顶元素并与当前元素合并并继续判断接下来的栈顶元素与当前元素的 gcd \gcd gcd是否为 1 1 1直到不为一或栈为空。最后看栈内元素是否为 1 1 1即可。
但在合并的过程中 a i a_i ai会很大甚至连 i n t 128 int128 int128都可能存不下。而 700 700 700以内的质数只有 125 125 125个我们可以用 b i t s e t bitset bitset来存 a i a_i ai有哪些质因子。
虽然用了 b i t s e t bitset bitset但还是要枚举每个 a i a_i ai是否有每个质因数所以时间复杂度为 O ( n p ) O(np) O(np)其中 p p p为 700 700 700以内质数的个数也就是 125 125 125。
code
#includebits/stdc.h
using namespace std;
const int N700;
int n,q1,a[100005],r[100005],z[705],p[705],q[100005];
bitset130v[100005];
void init(){for(int i2;iN;i){if(!z[i]) p[p[0]]i;for(int j1;jp[0]i*p[j]N;j){z[i*p[j]]1;if(i%p[j]0) break;}}
}
int main()
{init();scanf(%d,n);for(int i1;in;i){scanf(%d,a[i]);for(int j1;a[i]1jp[0];j){if(a[i]%p[j]0) v[i][j-1]1;while(a[i]%p[j]0) a[i]/p[j];}}for(int i1;in;i){q[q1]i;while(q12(v[q[q1]]v[q[q1-1]]).count()){v[q[q1-1]]|v[q[q1]];--q1;}}if(q11) printf(Yes);else printf(No);return 0;
}
