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