首页 > 代码库 > 【BZOJ 3136】 3136: [Baltic2013]brunhilda (数论?)

【BZOJ 3136】 3136: [Baltic2013]brunhilda (数论?)

3136: [Baltic2013]brunhilda

Time Limit: 40 Sec  Memory Limit: 128 MB
Submit: 238  Solved: 73
[Submit][Status][Discuss]

Description

给定m个素数和Q个询问。每个询问有n个人,每次操作可以任意选择其中的一个素数p(素数可以重复使用),然后去掉剩余人数 mod p个人。对于每个询问,我们想知道,至少需要多少步操作才能去掉所有人。

Input

第一行:素数个数m和询问个数Q1 <= m <= 100 0001 <= Q <= 100 000)第二行:m个素数pi (2 <= pi <= 10 000 000)下面Q行:n (1 <= n <= 10 000 000

Output

Q行答案。如果无解,输出oo

Sample Input

2 2
2 3
5
6


Sample Output

3
oo

HINT

Source

abcdabcd987提供

 
【分析】
  40s。。你知道我有多大胆一开始还带个log做么。。。【最后T了一次,卡时过。。
  然后膜了一下栋爷爷:

首先每次都去掉尽量多的人,可以证明这样贪心是最优的 
然后递推,f[i]表示i最少操作多少次到0,j表示当前离i最远的i-i%p[x]的点,f[i]=f[j]+1,如果j不满足条件了就要向后找j 
易知j一定是p[x]的倍数,预处理出每个数最小的质因数minp,对于i是不是p[x]的倍数只要看minp和i/minp是否是p[x]的倍数

时间复杂度O(n)

 

  那个贪心是因为f数组显然是递增的。然后我只能想到倍数之前了。

  后面那个好厉害,就是说那个j代表的质数能影响的长度不能超过这个质数本身,所以弄一个l表示那个数最远到那里。那就要看他是哪几些质数的倍数,然后选最大那个。

  就是max(l[x/mn[x]],l[mn[x]]) mn表示x的最小质因子【这里猴赛雷啊。。

 

技术分享
 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<cstring>
 4 #include<iostream>
 5 #include<algorithm>
 6 using namespace std;
 7 #define Maxn 10001000
 8 #define Maxm 100010
 9 
10 inline int read()
11 {
12     int x=0,f=1;char ch=getchar();
13     while(ch<0||ch>9){if(ch==-)f=-1;ch=getchar();}
14     while(ch>=0&&ch<=9){x=x*10+ch-0;ch=getchar();}
15     return x*f;
16 }
17 
18 // int mymax(int x,int y) {return x>y?x:y;}
19 
20 int f[Maxn],mx;
21 int p[Maxm],q[Maxm];
22 
23 int pri[Maxn/10],pl,mn[Maxn],l[Maxn];
24 inline void init()
25 {
26     pl=0;
27     memset(l,0,sizeof(l));
28     mn[1]=1;
29     for(int i=2;i<=mx;i++)
30     {
31         if(!l[i]) pri[++pl]=i,mn[i]=i;
32         for(int j=1;j<=pl;j++)
33         {
34             if(pri[j]*i>mx) break;
35             mn[i*pri[j]]=pri[j];
36             l[i*pri[j]]=1;
37             if(i%pri[j]==0) break;
38         }
39     }
40 }
41 
42 int main()
43 {
44     int n,m;
45     scanf("%d%d",&n,&m);
46     for(int i=1;i<=n;i++) p[i]=read();
47     for(int i=1;i<=m;i++) q[i]=read(),mx=mx>q[i]?mx:q[i];
48     // for(int i=1;i<=n;i++) scanf("%d",&p[i]);
49     // for(int i=1;i<=m;i++) scanf("%d",&q[i]);mx=mx>q[i]?mx:q[i];
50     init();
51     // memset(l,0,sizeof(l));
52     // memset(f,0,sizeof(f));
53     for(int i=1;i<=mx;i++) l[i]=f[i]=0;
54     l[0]=0;
55     for(int i=1;i<=n;i++) l[p[i]]=p[i],l[0]=l[0]>p[i]?l[0]:p[i];
56     
57     int j=0;
58     for(int i=1;i<=mx;i++)
59     {
60         while(!l[j]||i-j>=l[j])
61         {
62             j++;
63             if(i==j) {mx=i-1;break;}
64         }
65         f[i]=f[j]+1;
66         // l[i]=mymax(l[i/mn[i]],l[mn[i]]);
67         l[i]=l[i/mn[i]]>l[mn[i]]?l[i/mn[i]]:l[mn[i]];
68     }
69     for(int i=1;i<=m;i++)
70     {
71         if(q[i]>mx) printf("oo\n");
72         else printf("%d\n",f[q[i]]);
73     }
74     return 0;
75 }
View Code

【那些20几秒咋做的啊?

 

2017-03-26 21:57:30

【BZOJ 3136】 3136: [Baltic2013]brunhilda (数论?)