网站特色,网站建设阿华seo,医院网站建设价值和意义,网站建设 职位题目链接#xff1a;http://acm.hdu.edu.cn/showproblem.php?pid5317 题意#xff1a;F(x) 表示x的不同质因子的个数结果是求L#xff0c;R区间中最大的gcd( F(i) , F(j) )#xff0c;i、j在L#xff0c;R区间内。 思路#xff1a;因为2L R1000000#xf…题目链接http://acm.hdu.edu.cn/showproblem.php?pid5317 题意F(x) 表示x的不同质因子的个数结果是求LR区间中最大的gcd( F(i) , F(j) )i、j在LR区间内。 思路因为2L R1000000所以他们的质因子最多的个数也就7个也就是说1F(x)7因为要求最大的GCD所以只要知道在LR区间内每个F(x)的情况就可以知道结果。 代码 1 #include stdio.h2 #include string.h3 #include iostream4 #include algorithm5 using namespace std;6 7 const int X1000010;8 bool isPrime[X1];9 int total;//计数
10 int prime[79000];
11 void getPrime()
12 {
13 total0;
14 memset(isPrime,true,sizeof(isPrime));
15 memset(prime,0,sizeof(prime));
16 for(int i2;iX;i)
17 {
18 if(isPrime[i]) prime[total]i;
19 for(int j0; jtotal i*prime[j]X; j)
20 {
21 isPrime[i*prime[j]]false;
22 if(i%prime[j]0)
23 break;
24 }
25 }
26 }
27
28 int dp[X][9];
29 int num[X];
30 void getCot()
31 {
32 memset(num,0,sizeof(num));
33 for(int i0;prime[i]1000000;i)
34 for(int jprime[i];j1000000;jprime[i])
35 num[j];
36 }
37
38 void gao()
39 {
40 memset(dp,0,sizeof(dp));
41 dp[2][1]1;
42 for(int i3;i1000000;i)
43 {
44 int ansnum[i];
45 for(int j1;j7;j)
46 dp[i][j]dp[i-1][j];
47 dp[i][ans];
48 }
49 }
50 int main()
51 {
52 int T,l,r,aa[10],ma;
53 getPrime();
54 getCot();
55 gao();
56 scanf(%d,T);
57 while(T--)
58 {
59 ma1;
60 scanf(%d%d,l,r);
61 for(int i1;i7;i)
62 {
63 aa[i]dp[r][i]-dp[l-1][i];
64 if(aa[i]2ima)
65 mai;
66 }
67 if(aa[6]0aa[3]0)
68 mamax(ma,3);
69 else if(aa[6]0aa[2]0||aa[4]0aa[2]0)
70 mamax(ma,2);
71 printf(%d\n,ma);
72 }
73 return 0;
74 } View Code 转载于:https://www.cnblogs.com/yjx-xx/p/4690556.html
