poj2886[反素数+线段树]

发表于 | 分类于 ， ， | 阅读数 次

链接:poj2886[反素数+线段树]

题解

  • 重点是求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
    #include<iostream>
    #include<cstdio>
    #include<cmath>
    #include<cstdlib>
    #include<cstring>
    #include<algorithm>
    #define rep(i,x,y) for(register int i=x;i<=y;++i)
    #define repd(i,x,y) for(register int i=x;i>=y;--i)
    #define ll long long
    #define lson o<<1,l,mid
    #define rson o<<1|1,mid+1,r
    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;
    }