hdu 5317 RGCDQ (dp+筛法)

hdu 5317 RGCDQ (dp+筛法)

分析：直接分解再而重循环肯定超时。

需要从素因子的个数入手，换个角度思考。 在1——1e6的范围内最多有7个素数相乘。1 2 3 4 5 6 7中有非素数1 4 6。

设素数个数是i的数字的个数是sum[i]

那么sum[4]的个数得加到sum[2]与sum[1]上，sum[6] 的个数加到sum[1]，sum[2]，sum[3]上

计算sum[i]:

for i , get f[i] and refresh dp[i][j]=dp[i-1][j]

dp[i][f[i]]++;

sum[i]=dp[r][i]-dp[l-1][i]

最后，从高到底遍历7——1，sum[i]>=2，则取之。（由直接求解转化为素因子个数问题）

#include #include #include #include using namespace std; const int N=1e6+10; typedef long long LL; int f[N]; int dp[N][10]; int sum[10]; void init(){ for(int i=2;i>t; while(t--){ scanf("%d%d",&l,&r); for(int i=1;i<=7;i++){ sum[i]=dp[r][i]-dp[l-1][i]; } sum[1]+=sum[4]+sum[6]; sum[2]+=sum[4]+sum[6]; sum[3]+=sum[6]; if(sum[7]>=2) puts("7"); else if(sum[6]>=2) puts("6"); else if(sum[5]>=2) puts("5"); else if(sum[4]>=2) puts("4"); else if(sum[3]>=2) puts("3"); else if(sum[2]>=2) puts("2"); else puts("1"); } return 0; }

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。