作者:薇洁诗婷梦添 | 来源:互联网 | 2023-10-09 21:12
小Q非常喜欢数学,但是他的口算能力非常弱。因此他找到了小T,给了小T一个长度为
nn的正整数序列
a1,a2,...,ana1,a2,...,an,要求小T抛出
mm个问题以训练他的口算能力。
每个问题给出三个正整数
l,r,dl,r,d,小Q需要通过口算快速判断
al×al+1×...×ar−1×aral×al+1×...×ar−1×ar是不是
dd的倍数。
小Q迅速地回答了出来,但是小T并不知道正确答案是什么,请写一个程序帮助小T计算这些问题的正确答案。
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
题目大意:给出n个数,每次给出一个区间l,r,一个X问 a[l-r]相乘是不是X得倍数,询问次数较多
很容易想到质因数分解,然后再比较l,r之间的每个质因数的个数与X的每个质因数的个数相比较
如果x的一个质因数的个数>l到r里某个质因数的个数,肯定是不行的,具体实现起来不知道怎么实现
参考了网上的题解,大概写一下过程吧
#include
#include
#include
#include
#include
#include
#define LL long long
using namespace std;
const int maxn=100005;
vectorG[maxn];
void work(int id,int k)//首先将输入的n个数进行质因数分解
{
for(int i=2;i*i<=k;i++)//G[x]含有质因数x的下标
{
while(k%i==0)
{
G[i].push_back(id);
k/=i;
}
}
if(k>1)G[k].push_back(id);//这里注意一下
}
int query(int l,int r,int x)//下标是按照非严格递增排序的直接二分查找
{
int t1=upper_bound(G[x].begin(),G[x].end(),r)-G[x].begin();
int t2=lower_bound(G[x].begin(),G[x].end(),l)-G[x].begin();
return t1-t2;
}
void init()//这里可以只清空下标为质数的容器
{
for(int i=0;iquery(l,r,j))
{
f=1;
break;
}
}
if(tem>1&&query(l,r,tem)==0)//这里判断tem本身是个质数
{
f=1;
}
if(f)
{
printf("No\n");
}
else printf("Yes\n");
}
init();
}
return 0;
}
/*
G[2] 1 2 2 4
G[3] 1
G[5] 5
G[7] 7
注意:
upper_bound 是返回第一个大于val的位置不能等于而lowwer——bound 是返回第一个小于等于val的元素。
*/https://blog.csdn.net/ZscDst/article/details/80497236