题解
- 重点是求n以内因数个数最大的数及其个数,一开始的做法是用欧拉线性筛,然后打个表,然后看了题解发现有一个神奇的东西叫反素数。
- 学习了一波然后用更快的方法打了个表23333(好像没啥用…)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
using namespace std;
const int N=5e5+7;
int rev[37] = {1,2,4,6,12,24,36,48,60,120,180,240,360,720,840,1260
,1680,2520,5040,7560,10080,15120,20160,25200,27720,45360,50400,55440,83160,
110880,166320,221760,277200,332640,498960,500001};
int revs[37] = {1,2,3,4,6,8,9,10,12,16,18,20,24,30,32,36,40,48,60,64,72,
80,84,90,96,100,108,120,128,144,160,168,180,192,200,1314521};
int tr[N<<2],w[N],pos,n,k,id;
char str[N][20];
inline void build(int o,int l,int r){
tr[o]=r-l+1;
if(l==r)return ;
int mid=l+r>>1;
build(lson);
build(rson);
}
inline int update(int o,int l,int r,int x){
tr[o]--;
if(l==r)return l;
int mid=l+r>>1;
if(x<=tr[o<<1])return update(lson,x);
return update(rson,x-tr[o<<1]);
}
int main(){
while(~scanf("%d%d",&n,&k)){
while(rev[id]<=n)id++;
rep(i,1,n)scanf("%s%d",str[i],&w[i]);
build(1,1,n);
int &p=tr[1];pos=0;
int m=rev[id-1];
rep(i,1,m){
if(w[pos]>0)k=((k+w[pos]-2)%p+p)%p+1;
else k=((k+w[pos]+p-1)%p+p)%p+1;
pos=update(1,1,n,k);
}
printf("%s %d\n",str[pos],revs[id-1]);
}
return 0;
}