2018 CCPC女子学生専用場HDU 6287口算訓練オーラ関数+二分


試合の時にオラ関数を使いたいと思ったのですが、区間照会部分をどのように最適化するか分からず、スケジュールを見てやっと気づきました...料理が多すぎて...何もできない
構想は主に質量因数分解+二分である.a 1,a 2,...,anは各数について素因数分解を行い,配列aで素数xが配列中に左から右に現れる位置を格納し,質問二分毎に区間に何個の素数xがあるかを求める.配列が大きすぎてvectorで格納することに注意してください.
詳しい構想は書かないで、コードの中で多くの注釈の地方があって、読めないのは注釈の出力の中間変数を取り消して見て、以下はACコードです:
#include
#include
#include
#include
#include
using namespace std;

const int MAX=100010;
int n,m;
int L,R;
vectora[MAX];

void euler(int n,int x)//    , x       i
{
    for(int i=2;i*i<=n;i++)
        while(n%i==0)
        {
            a[i].push_back(x);
            n/=i;
        }
    if(n>1)
        a[n].push_back(x);
}

bool ask(int x,int k)
{
    //a[x]:     x     
    int l=0,r=a[x].size()-1;
    int t=-1,mid;
    //cout<>1;
        //cout<=L)
            r=(t=mid)-1;
        else
            l=mid+1;
        //cout<r)//    
            return false;
        if(a[x][t]>R)//    
            return false;
        t++;
    }
    return true;
}

bool solve(int n)
{
    for(int i=2;i*i<=n;i++)
        if(n%i==0)
        {
            int num=0;
            while(n%i==0)
                n/=i,num++;
            //cout<