傳送門(mén)
題目：

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

分析：
直接暴力TLE……
需要換一種思路！
在$10^5$中質(zhì)因數(shù)組成的個(gè)數(shù)不會(huì)很多，所以可以將質(zhì)數(shù)定為下標(biāo)，通過(guò)對(duì)a[i]分解質(zhì)因數(shù)x,若a[i]里質(zhì)數(shù)x有num個(gè)則將下標(biāo)i存入x里,且存num個(gè)i；
通過(guò)二分查詢對(duì)應(yīng)下標(biāo)看個(gè)數(shù)是否夠即可判斷；

代碼：

#include<bits/stdc++.h>using namespace std; typedef long long ll; //#define int long long const int N=1e5+10; const ll mod=1e+7; #define eps 1e-8 int cnt=1; int a[N]; vector<int>s[N]; void dev(int x,int pos){//分解質(zhì)因數(shù)int c=sqrt(x); // cout<<"pos="<<pos;for(int i=2;i<=c;i++){while(x%i==0){s[i].push_back(pos);x/=i; // cout<<i<<' ';}}if(x>1){s[x].push_back(pos); // cout<<x;} // cout<<endl; } signed main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t,n,m,l,r,d;cin>>t;while(t--){cin>>n>>m;for(int i=2;i<100000;i++)vector <int>().swap(s[i]); for(int i=1;i<=n;i++){cin>>a[i]; // cout<<"a[]="<<a[i]<<endl;dev(a[i],i);}while(m--){cin>>l>>r>>d;int c=sqrt(d);int flag=0;for(int i=2;i<=c;i++){int num=0;while(d%i==0){num++;d/=i;}if(num){if(!s[i].empty()){int fi=lower_bound(s[i].begin(),s[i].end(),l)-s[i].begin();int ed=upper_bound(s[i].begin(),s[i].end(),r)-s[i].begin(); // cout<<"i="<<i<<" fi="<<fi<<" ed="<<ed<<endl;if(ed-fi<num){flag=1;break;}}else{flag=1;break;}}}if(d>1){int fi=lower_bound(s[d].begin(),s[d].end(),l)-s[d].begin();int ed=upper_bound(s[d].begin(),s[d].end(),r)-s[d].begin();if(ed-fi<1)flag=1;}if(flag)cout<<"No";else cout<<"Yes"; // if(m>0)cout<<endl;} // if(t>0) // cout<<endl;}return 0; }

總結(jié)

以上是生活随笔為你收集整理的口算训练（思维）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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