Solution

可以发现实际上是把n分为几个循环节，然后找循环节的\(lcm\)是这次的排数

而\(lcm\)必然是一些最高次幂的质数的成积，那么就dp求一下所有情况就好了

PS:注意并不是必须要等于n小于n都行，因为可以在后面补1而\(lcm\)不变

Code

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #define Re register#define int long long#define F(i,a,b) for(Re int i=(a);i<=(b);i++)#define R(i,a,b) for(Re int i=(b);i>=(a);i--)using namespace std;inline int read() { int x=0,f=1;char c=getchar(); while(!isdigit(c)) {if(c=='-')f=-f;c=getchar();} while(isdigit(c)) x=(x<<1)+(x<<3)+c-48,c=getchar(); return x*f;}const int N=1010;bool vis[N];int n,tot,ans;int pri[N],f[N];void init() { F(i,2,n) { if(!vis[i]) pri[++tot]=i; for(Re int j=1;j<=tot&&i*pri[j]<=n;j++) { vis[i*pri[j]]=1; if(i%pri[j]==0) break; } }}signed main() { n=read(); init();// F(i,1,tot) printf("%d ",pri[i]);cout<