Category:二分数论
Little Q likes math very much, but his arithmetic ability is very weak. So he found the small T and gave the small T a lengthnnPositive integer sequencea1,a2,...,ana1,a2,…,an，Ask small T to throw outmmA problem is the ability to train his oral calculation. It

Three positive integers are given for each probleml,r,dl,r,d，Small Q needs to be quickly judged by oral calculational×al+1×...×ar1×aral×al+1×…×ar−1×arIs it right?ddThe multiple of the number. It

Little Q answered quickly, but little T did not know what the correct answer was, please write a program to help small T calculate the correct answers to these questions.

InputThe first line contains a positive integerT(1T10)T(1≤T≤10)，The number of groups that represent the test data. It

The first line of each group contains two positive integersn,m(1n,m100000)n,m(1≤n,m≤100000)，The length of the sequence and the number of the problems are represented respectively. It

The second line containsnnPositive integera1,a2,...,an(1ai100000)a1,a2,…,an(1≤ai≤100000)，Each number in a sequence is represented. It

NextmmRow, three positive integers per linel,r,d(1lrn,1d100000)l,r,d(1≤l≤r≤n,1≤d≤100000)，Express each problem.OutputFor each problem output a row, if multiples, output Yes, otherwise output 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
YesTwo points + unique decomposition theorem, first based on the a[n] array of the quality factor (unique decomposition theorem) to establish the vector array, and then judge the number of the quality factor of D and the number of a factor in the number of [l, R]Size (two point operation)c++ code:
#include<bits/stdc++.h>

using namespace std;

const int N=1e5+10;
vector<int>v[N];

void LK(int val,int n)
{
for(int i=2;i*i<=val;i++)
{
if(val%i==0)
{
while(val%i==0)
{
val/=i;
v[i].push_back(n);
}
}
}
if(val!=1)
v[val].push_back(n);
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n,m;
for(int i=0;i<N;i++)
{
v[i].clear();
v[i].push_back(0);
}
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
int val;
scanf("%d",&val);
LK(val,i);
}
for(int i=0;i<N;i++)
v[i].push_back(n+1);
while(m--)
{
int l,r,d,ans=0;
int flag=1;
scanf("%d%d%d",&l,&r,&d);
for(int i=2;i*i<=d;i++)
{
if(d%i==0)
{
while(d%i==0)
{
d/=i;
ans++;
}
int left=lower_bound(v[i].begin(),v[i].end(),l)-v[i].begin();
int right=upper_bound(v[i].begin(),v[i].end(),r)-v[i].begin()-1;
//    cout<<left<<" "<<right<<endl;
if(right<left||right-left+1<ans)
{
flag=0;
break;
}
ans=0;
}
}
if(d!=1)
{
int left=lower_bound(v[d].begin(),v[d].end(),l)-v[d].begin();
int right=upper_bound(v[d].begin(),v[d].end(),r)-v[d].begin()-1;
//    cout<<left<<" "<<right<<endl;
if(right<left||right-left+1<ans)
flag=0;
}

if(flag)
puts("Yes");
else
puts("No");
}
}
return 0;
}

Q, a famous topic maker, has had a lot of questions. During this long process, he found that it is very painful to determine the range of data. It

Whenever considering the time efficiency of a topic, small Q needs to set a reasonable data range by combining time limits and evaluation machine configuration. It

Because it is a painful matter to determine the scope of data, after small Q has produced many questions, no data scope is set up. For a topic, little Q will tell you that the time complexity of his algorithm isO(nalogbn)O(nalogb⁡n)，And contained in this bigOOThe constant under the mark is11。At the same time, small Q will tell you that the evaluation machine can be executed within the specified time limit.kkArticle instructions. Small Q thinks so long asna(log2n)bna(⌈log2⁡n⌉)bnot exceedingkk，So it’s a reasonable range of data. Among them,x⌈x⌉The smallest is not less thanxxThe positive integer, that is,xxTake it up. It

Nature, small Q wants the scope of the datannThe bigger the better, he wants you to write a program to help him set the maximum data range.

InputThe first line contains a positive integerT(1T1000)T(1≤T≤1000)，The number of groups that represent the test data. It

Each group of data contains a row of three positive integersa,b,k(1a,b10,106k1018)a,b,k(1≤a,b≤10,106≤k≤1018)，The time complexity and the number of instructions are described respectively.OutputFor each group of data, output one line and one positive integernn，That is the greatest possiblenn。Sample Input

3
1 1 100000000
2 1 100000000
1 3 200000000

Sample Output

4347826
2886
48828Two points, pay attention to log () to write, and control number overflow.c++ code:
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const ll llf=(1e18)+10;

ll log(ll n)
{
ll i=0,ans=1;
while(ans<n)
{
ans<<=1;
i++;
}
return i;
}
ll LK(ll a,ll b,ll n,ll k)
{
ll log2=log(n);
ll ans=1;
for(int i=0;i<a;i++)
{
if(ans>(k+1)/n)   return k+1;   // Control number spillover
ans*=n;
}
if(log2==0) return 0;
for(int i=0;i<b;i++)
{
if(ans>(k+1)/log2)   return k+1; // Control number spillover
ans*=log2;
}
return ans;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
ll a,b,k;
scanf("%lld%lld%lld",&a,&b,&k);
int flag=0;
ll l=1,r=llf,po=0;
while(l<=r)
{
ll mid=(l+r)>>1;
if(LK(a,b,mid,k)<=k)
{
po=mid;
l=mid+1;
}
else
r=mid-1;
}
printf("%lld\n",po);
}
return 0;
}