2018 ccpc女生赛 口算训练 （二分 + 唯一分解定理）

本文主要是介绍2018 ccpc女生赛 口算训练 （二分 + 唯一分解定理），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Input第一行包含一个正整数 T(1≤T≤10)T(1≤T≤10)，表示测试数据的组数。 

每组数据第一行包含两个正整数 n,m(1≤n,m≤100000)n,m(1≤n,m≤100000)，分别表示序列长度以及问题个数。 

第二行包含 nn个正整数 a1,a2,...,an(1≤ai≤100000)a1,a2,...,an(1≤ai≤100000)，表示序列中的每个数。 

接下来 mm行，每行三个正整数 l,r,d(1≤l≤r≤n,1≤d≤100000)l,r,d(1≤l≤r≤n,1≤d≤100000)，表示每个问题。Output对于每个问题输出一行，若是倍数，输出Yes，否则输出No。Sample Input

1
5 4
6 4 7 2 5
1 2 24
1 3 18
2 5 17
3 5 35

Sample Output

Yes
No
No
Yes

先用vector记录下每个因子出现的位置。vector里存的是含有i这个因子的下标。

查找l到r里因子个数时用upper_bound() - lower_bound()就可以。 

#include<bits/stdc++.h>
using namespace std;
vector<int> a[100005];
int T, n, m;
void init(int x, int Index){for(int i = 2; i * i <= x; i++){if(x % i == 0){while(x % i == 0){x /= i;a[i].push_back(Index);}}}if(x > 1)a[x].push_back(Index);
}int query(int l, int r, int x){return upper_bound(a[x].begin(), a[x].end(), r) - lower_bound(a[x].begin(), a[x].end(), l);
}int judge(int l, int r, int x){for(int i = 2; i * i <= x; i++){if(x % i == 0){int t = 0;while(x % i == 0){x /= i;t++;}int c = query(l, r, i);if(t > c)return 0;}}if(x > 1 && query(l, r, x) < 1)return 0;return 1;
}int main()
{scanf("%d", &T);while(T--){for(int i = 0; i < 100005; i++)a[i].clear();scanf("%d%d", &n, &m);for(int i = 1; i <= n; i++){int x;scanf("%d", &x);init(x, i);}for(int i = 0; i < m; i++){int l, r, d;scanf("%d%d%d", &l, &r, &d);int flag = judge(l, r, d);if(flag)printf("Yes\n");elseprintf("No\n");}}return 0;
}

这篇关于2018 ccpc女生赛 口算训练 （二分 + 唯一分解定理）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---