写代码的时间长达3个半小时,当然没刨去中间吃饭什么的........
思路:先直接dfs求出最大的 p 和 f(p) 这里用到了反素数,详解请看zoj 2562那篇文章,里面有解释
然后就是用线段树模拟约瑟夫,但是悲剧的是我没太搞懂出圈顺序,此处系参考而来....................
code
#include <iostream> #include <fstream> #include <cstdio> #include <algorithm> #include <cstring> #include <string> #include <string.h> #include <vector> #include <bitset> #include <cmath> #include <queue> #include <stack> #include <set> #include <ctime> #include <map> #include <limits> #define LL long long #define Vi vector<int> #define Si set<int> #define readf freopen("input.txt","r",stdin) #define writef freopen("output.txt","w",stdout) #define FF(i,a) for(int i(0); i < (a); i++) #define FD(i,a) for(int i(a); i >= (1); i--) #define FOR(i,a,b) for(int i(a);i <= (b); i++) #define FOD(i,a,b) for(int i(a);i >= (b); i--) #define PD(a) printf("%d",a) #define SET(a,b) memset(a,b,sizeof(a)) #define SD(a) scanf("%d",&(a)) #define LN printf("\n") #define PS printf(" ") #define pb push_back #define lson l , m , rt << 1 #define rson m + 1 , r , rt << 1 | 1 const double pi = acos(-1.0); const int maxn = 500001; const int INF = 99999999; const int dx[]={0,1,0,-1}; const int dy[]={1,0,-1,0}; using namespace std; struct stu{ char name[20]; int val; }p[maxn]; int prime[7]={2,3,5,7,11,13,17}; int N,K; int ans,mcnt; //ans为最大的反质数,mcnt为最大反质数的因子数 void dfs(int num,int cnt,int k,int lim){ if(k>7) return; if(cnt>mcnt){ mcnt=cnt; ans=num; } if(cnt==mcnt && num<ans) ans=num; int tmp=num; FOR(i,1,lim){ if(tmp*prime[k]>N) return ; tmp*=prime[k]; dfs(tmp,cnt*(i+1),k+1,i); } } int len[maxn<<2]; void PushUP(int rt){ len[rt]=len[rt<<1]+len[rt<<1|1]; } void build(int l,int r,int rt){ if(l==r){ len[rt]=1; return ; } int m=(l+r)>>1; build(lson); build(rson); PushUP(rt); } int query(int p,int l,int r,int rt){ if(l==r){ len[rt]=0; return l; } int m=(l+r)>>1; int ret; if(p<=len[rt<<1]) ret=query(p,lson); else ret=query(p-len[rt<<1],rson); PushUP(rt); return ret; } int main() { int &mod=len[1]; while(~scanf("%d%d",&N,&K)){ ans=N;mcnt=0; dfs(1,1,0,20); FOR(i,1,N) scanf("%s%d",p[i].name,&p[i].val); build(1,N,1); int pos; FOR(i,0,ans-1) { if(p[pos].val>0) K=((K+p[pos].val-2)%mod+mod)%mod+1; // else K=((K+p[pos].val-1)%mod+mod)%mod+1; //说实话这个真心不懂 pos=query(K,1,N,1); } printf("%s %d\n",p[pos].name,mcnt); } return 0; }