这道题目比较经典,或者说这种思想比较经典。
这种筛法的思想。
我们正着想对于每一个\(n、 n-1、n-2、...、2、1\)都分解一遍质因数显然是来不及的时间复杂度达到\(O(n \sqrt{n})\)
我们考虑对于每一个1e6以内的质因数的个数
跑了一下程序是\(78498\)个
素数定理告诉我们不超过x的素数近似有\(\frac{x}{lnx}\)个
对于每一个质因子我们看一下那些数有一个这个质因子,那些数有两个,那些数有3个这个每次是平方的增长很快
时间复杂度:\(O(\frac{n}{logx} * logn)\)近似\(O(n)\)
#include <bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(int i = (a); i >= (b); --i)
#define pii pair<int, int>
#define pll pair<long long, long long>
#define ll long long
#define db double
#define endl '\n'
#define x first
#define y second
#define pb push_back
using namespace std;
const int N=1e6+10,mod=1e9+7;
int vis[N];
vector<int>p;
void solve()
{
int n;cin>>n;
auto get=[&](int x){
rep(i,2,x){
if(!vis[i]) p.pb(i);
for(int j=0;p[j]*i<=x;++j){
vis[i*p[j]]=1;
if(i%p[j]==0) break;
}
}
};
get(1e6);
cout<<p.size()<<endl;
int res=0;
vector<int>ans(n+1);
rep(i,0,p.size()-1){
for(int j=p[i];j<=n;j*=p[i]){
ans[i]+=n/j;
res+=n/j;
}
}
rep(i,0,p.size()-1){
cout<<p[i]<<' '<<ans[i]<<endl;
}
return;
}
signed main(){
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
// freopen("1.in", "r", stdin);
int _;
// cin>>_;
// while(_--)
solve();
return 0;
}
标签:题目,筛法,思想,int,rep,long,数有,define
From: https://www.cnblogs.com/cxy8/p/18012012