一道大水题 题解

常规
,
1

根据题目，这道题很水，实际上一点都不难。
首先你要知道，这道题考的是数学，而并不是图论，这题可以建边，但没必要，建边反而会增加至少O(nlog(n))的复杂度（虽然不建边程序也至少有O(nlog(n)））

首先进行一个欧拉筛（我用的aishishai）筛出质数打表万岁。然后我用的dp来算出每个点的情况数。（我听一些大佬说用拓扑也行）

#include<bits/stdc++.h>
using namespace std;
//s记录每个要查询的点，f就是dp数组
long long n,q,s[5000005],f[5000005],r,w;
bool prt[500005];
//prt表示谁是质数
long long inf=1e9+7;

int main(){
  cin >> n >> q;
  for(int i=1; i<=q; i++){//输入
    cin >> s[i];
    w=max(s[i],w);//记录最大的查询值（代替n）
    //这样有一些优化，但不多
  }
  prt[1]=1;
  prt[0]=1;
  for(int i=2; i<=w; i++){//筛质数
    if(!prt[i])
    for(int j=2; j*i<=w; j++){
      prt[i*j]=true;
    }
  }
  f[1]=1;//1号点有一种情况
  for(int i=1; i<=w; i++){
    for(int j=2; j*i<=w; j++){
      if(!prt[j])
        f[i*j]=(f[i]+f[i*j])%inf;//如果能到这个点就加上过来的点的情况
    }
  }
  
  for(int i=1; i<=q; i++){
    cout << f[s[i]]%inf << endl;
  }
  
  return 0;
}
2 个赞