期望DP

 

一个数只能分解成不大于它的数，那么转移构成拓扑关系。

 

试了一下预处理出不大于x的质数个数，然而程序并没有变快

1 /*by SilverN*/ 2 #include
     
       3 #include
      
        4 #include
       
         5 #include
        
          6 #include
         
           7 #include
          
            8 using namespace std; 9 const int mxn=1000100;10 int read(){11 int x=0,f=1;char ch=getchar();12 while(ch<'0' || ch>'9'){ if(ch=='-')f=-1;ch=getchar();}13 while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}14 return x*f;15 }16 double f[mxn];17 int pri[mxn],cnt=0,sum[mxn];18 bool vis[mxn];19 void init(){20 for(int i=2;i