#include <cstdio> #include <vector> #include <algorithm> #include <iostream> using namespace std; const int N = 1e5 + 5; vector<int> prime[N];//二維的質(zhì)因數(shù)容器，每個prime[N]存的是輸入序列中的下標//二分法查找質(zhì)因數(shù)，用lower_bound和upper_bound函數(shù) int query(int i, int l, int r) {return upper_bound(prime[i].begin(), prime[i].end(), r) - lower_bound(prime[i].begin(), prime[i].end(), l);//在目標序列段：[右邊的最后一個數(shù)]下標-[左邊第一個數(shù)]下標 } /* 1、查找目標數(shù)的質(zhì)因子,先cnt=0,再while，cnt++累加相同質(zhì)因子的個數(shù) 2、每找完一個因子數(shù)，就跟prime[N]中的指定序列的因子個數(shù)相比，小于則false 3、如果目標數(shù)本身是質(zhì)數(shù)、或者數(shù)太小進不去for循環(huán)、或者cnt一直=0，都會錯過上面的false條件，所以要用新的if判斷， 當(dāng)目標數(shù)不為1且目標數(shù)本身在輸入序列質(zhì)因子中不存在，返回false */ bool half_find(int l, int r, int d) {for (int i = 2; i*i <= d; i++) {int cnt = 0;//每次循環(huán)先置為0while (d%i == 0) {d /= i;//目標數(shù)變小cnt++;}if (cnt > query(i, l, r)) return false;//每一個數(shù)判斷一次，目標數(shù)的該因子是否大于序列數(shù)的該因子}if ((d != 1) && (query(d, l, r) < 1)) return false;//三種情況：數(shù)太小進不去for循環(huán)、d為質(zhì)數(shù)、排除了“任何數(shù)都是1的倍數(shù)”的情況return true; }int main() {int T, n, m, a[N];int l, r, d;scanf("%d", &T);while (T--) {scanf("%d %d", &n, &m);for (int i = 1; i < N; i++) {prime[i].clear();//清空vector!!!}for (int i = 1; i <= n; i++) {//題目是從1開始scanf("%d", &a[i]);for (int j = 2; j*j <= a[i]; j++) {//注意是從2開始的while (a[i] % j == 0) {a[i] /= j;//序列數(shù)變小prime[j].push_back(i);//在prime[因子]中放入序列的下標（for循環(huán)會導(dǎo)致下標按順序存儲）}}if (a[i] > 1) prime[a[i]].push_back(i);//如果目標數(shù)是質(zhì)數(shù)、或者目標數(shù)進不去for循環(huán)的情況,注意：存的是自己不是j}//輸入問題for (int k = 1; k <= m; k++) {scanf("%d %d %d", &l, &r, &d);if (half_find(l, r, d)) printf("Yes\n");else printf("No\n");}}return 0; }

Problem - 6287 (dingbacode.com)

總結(jié)

以上是生活随笔為你收集整理的CCPC2018女生赛口算训练6287的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。