SP11736 PTIME - Prime Time 题解

· · 题解

Upd：更新了标点符号问题。

因为 n! 十分巨大，所以我们需要使用一些小技巧。

根据同底数幂的乘法我们可以得出，n! 的分解质因数中，每个质数的指数就是 1 至 n 中所有数分解质因数中这个质数的指数之和。有了这一点本题就很好实现。

首先我们进行质数筛，将一定范围内的质数用欧拉筛全部筛出来。之后对 1 至 n 每个数进行分解质因数，最后加和即可。

放代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5;
int main(){
  ios::sync_with_stdio(false);
  int n; cin>>n;
  vector<bool> ip(N+1,true);
  ip[1]=false;
  vector<int> p;
  for(int i=2;i<=N;i++){
    if(ip[i])p.emplace_back(i);
    for(int j:p){
      if(1ll*i*j>N)break;
      ip[i*j]=false;
      if(!(i%j))break;
    }
  } // 质数筛
  vector<int> x(p.size());
  for(int i=1;i<=n;i++){
    int w=i;
    for(int j=0;p[j]<=i;j++)
      while(w%p[j]==0)x[j]++,w/=p[j];
  } // 暴力分解质因数
  for(int i=0;;i++){
    if(!x[i])break;
    else if(i)cout<<" * ";
    cout<<p[i]<<'^'<<x[i];
  } // 输出
  return 0;
}