Article From:https://www.cnblogs.com/lemon-jade/p/9125775.html
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
Yes


Two 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
48828

Two 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;
}

 

  

Similar Posts:

Leave a Reply

Your email address will not be published. Required fields are marked *