公式
G - P-smooth number 解説 by physics0523
ヒント: この問題の最後のサンプルは最大ケースです。
サンプルに最大ケースが入っている場合、そこから何らかの情報を読み取ったり最大ケースに対して正解できるかの判定が(提出前に)行えたりします。
この問題の場合、最大ケースの答えが \(2 \times 10^9\) 程度であることが分かります。ここから
- 全探索することはやや無謀である
- (例えば) 半分全列挙のような、効率的な探索ができたら実行時間制限に間に合いそうだ
という予想を得ます。ここでは半分全列挙を実現することを考えます。どのようにすればよいでしょうか ?
- 配列 \(U=(1),V=(1)\) を用意します。
- \(2\) 以上 \(P\) 以下の全ての素数 \(q\) について、以下を繰り返す。
- \(U,V\) のうち小さい方を \(W\) とし、 \(W\) に次のような操作を施す。
- \(W\) の各要素に \(q\) のべき乗を掛けたものであって、値が \(N\) 以下のものを全て \(W\) に追加する。
- \(U,V\) のうち小さい方を \(W\) とし、 \(W\) に次のような操作を施す。
- 最後に、半分全列挙におけるマージの要領で \(U,V\) の各配列から \(1\) 要素ずつ選択して掛けた時に \(N\) 以下となるような組の数を数え上げる。
つまり、 \(P\) 以下の素因数を適切に \(2\) つの集合に分けた上で、各集合内の素因数しか持たない数を列挙し、最後にそれらをマージして和集合内の素因数しか持たない数を数え上げています。
この解法の計算量を机上で見積もるのは困難ですが、実際に実装して最大ケースを試すと \(|U|,|V| \le 5 \times 10^6\) 程度で済むことがわかり、これらをソートして半分全列挙におけるマージをしても十分高速なことが分かります。
実装例 (C++):
#include<bits/stdc++.h>
using namespace std;
void step(vector<long long> &a,long long p,long long mxm){
long long sz=a.size();
for(long long i=0;i<sz;i++){
long long ad=a[i];
while(1){
ad*=p;
if(ad>mxm){break;}
a.push_back(ad);
}
}
}
int main(){
vector<long long> pl={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};
long long n,p;
cin >> n >> p;
while(p<pl.back()){pl.pop_back();}
vector<long long> u={1},v={1};
for(auto &nx : pl){
if(u.size()<v.size()){step(u,nx,n);}
else{step(v,nx,n);}
}
// cerr << u.size() << " " << v.size() << "\n";
sort(u.begin(),u.end());
sort(v.begin(),v.end());
long long res=0,j=v.size()-1;
for(long long i=0;i<u.size();i++){
long long mv=(n/u[i]);
while(j>=0 && mv<v[j]){j--;}
if(j<0){break;}
res+=(j+1);
}
cout << res << "\n";
return 0;
}
投稿日時:
最終更新: