poj 2886 Who Gets the Most Candies? （线段树模拟加强版约瑟夫问题+反素数)
题意：n个人围成一圈，每个人身上由一个数，可正可负。从第k个人开始出圈，如果第k个人身上的数是X,X>0，就左边第x个没有出圈的人出圈，否则右边第-X个人出圈。 第k个人出圈得到的糖果数目为f(k)，f(x)表示x的因子个数。现在问谁能拿到最多的糖果，并且拿到了多少糖果。
思路：看起来好像很麻烦。。其实可以分解成两个问题。
第一个子问题就是约瑟夫问题的加强版。。。每次间隔不是定数，而取决与上一次出队的人。。。
终点是数据有5E5.。。模拟的话会炸掉。。。所以用线段树来模拟这个过程。。。
类似于那道插队的问题。。。线段树的域存的是某区间中空位置的数量。。初始为1.。。
然后每次update的时候优先查看左子树。。。
第二个子问题就是。。。到底第几个出去的人那道的糖果最多。。。。
其实也就是求1..n中。。。因子数最大的那个。。。
利用反素数表。。。每次upper_bound一下即可。。。
/* ***********************************************
Author :111qqz
Created Time :Wed 21 Sep 2016 09:19:11 PM CST
File Name :code/poj/2886.cpp
************************************************ */
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair
using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int N=5E5+7;
int tree[N<<2];
int n,k;
char nam[N][11];
int val[N];
int s[40] = {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 b[40] = {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};
void PushUp( int rt)
{
tree[rt] = tree[rt<<1] + tree[rt<<1|1];
}
void build( int l,int r,int rt)
{
if (l==r)
{
tree[rt] = 1;
return;
}
int m = (l+r)>>1;
build(lson);
build(rson);
PushUp(rt);
}
int update( int p,int l,int r,int rt)
{
if (l==r)
{
tree[rt]--;
return l;
}
int m = (l+r)>>1;
int ret;
if (p<=tree[rt<<1]) ret = update(p,lson);
else ret = update(p-tree[rt<<1],rson);
PushUp(rt);
return ret;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("code/in.txt","r",stdin);
#endif
while (~scanf("%d%d",&n,&k))
{
ms(tree,0);
for ( int i = 1 ;i <= n ; i++) scanf("%s%d",nam[i],&val[i]);
build(1,n,1);
int id = upper_bound(s,s+40,n)-s-1;
int m = s[id];
int ans = b[id];
int num = n; //剩余人数
int pos;
for ( int i = 0 ; i < m ; i++)
{
num--;
pos = update(k,1,n,1);
if (num==0) break;
if (val[pos]>=0) k = (k-1-1+val[pos])%num+1; //先-1变成0based，最后+1变回1_based.
else k = ((k-1+val[pos])%num+num)%num+1;
}
printf("%s %d\n",nam[pos],ans);
}
return 0;
}
顺便再来个打反素数以及对应约数的表。
/* ***********************************************
Author :111qqz
Created Time :Wed 21 Sep 2016 05:14:13 PM CST
File Name :anti-prime.cpp
************************************************ */
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair
using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int NN=500015;
const int N=500005;
int noprime[NN],table[NN][2];
int T;
void init(){
ms(noprime,0);
for (int i=1;i<=N;++i){
for(int j=i;j<=N;j+=i)
++noprime[j];
}
T=0;
table[0][0]=1;
table[0][1]=1;
for (int i=2;i<=N;++i)
if (noprime[i]>table[T][1]){
table[++T][0]=i;
table[T][1]=noprime[i];
}
++T;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("code/in.txt","r",stdin);
#endif
init();
for ( int i = 1 ; i <= T ; i++) printf("%d %d\n",table[i][0],table[i][1]);
#ifndef ONLINE_JUDGE
fclose(stdin);
#endif
return 0;
}