poj2886 线段树单点修改+反素数(喵?)

Posted by Cww97 on 2017-07-05

版权声明:本文为博主原创文章,未经博主允许不得转载。原文所在http://blog.csdn.net/cww97 https://blog.csdn.net/cww97/article/details/74370016
### 题意:

n个熊孩子每个人有个数字a[i],首先k号熊孩子出圈,然后第k+a[i]个熊孩子出圈,一个环,可以绕很多圈,如果a[i]为正则顺时针数,反之逆时针,相当于一个变体的约瑟夫游戏,第i个出圈的熊孩子,有f[i]的得分,f[i]为i的因子个数

反正没人看的讲解:

分为两个部分:线段树模拟约瑟夫游戏+寻找1到n范围内因数数量最多的那个ans,约瑟夫游戏只要做到第ans个人出圈就好了

区间和的线段树,每个叶子节点为1,代表一个熊孩子,出圈置为0,

至于因子数量,my math is very poor,所以我搜了题解,看见标题里一群反素数,于是顺势百度了反素数,搜到反素数深度分析,第三道题正好就是这玩意,于是复制粘贴之(划掉),虽然到现在还不知道反素数是个什么玩意

似乎搜到的题解都是打表来解决的因数个数问题,

我真的debug了10个小时,心累

code

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1e7 + 7;
const LL INF = ~0LL;
const int prime[16] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};

struct child{
char name[11];
int val;
inline void read(){scanf("%s %d\n", name, &val);}
}arr[N];

LL maxNum, ansPos, n;

void dfs(int dep, LL tmp, int num){
if (dep >= 16) return;
if (num > maxNum){
maxNum = num;
ansPos = tmp;
}
if (num == maxNum && ansPos > tmp) ansPos = tmp;
for (int i = 1; i < 63; i++){
if (n / prime[dep] < tmp) break;
dfs(dep+1, tmp *= prime[dep], num*(i+1));
}
}

struct segmentTree
{
#define lc (rt<<1)
#define rc (rt<<1^1)
int val[N], M;

inline void build(int n){
M = 1; while(M<n) M<<=1; M--;
for (int leaf = 1+M; leaf <= n+M; leaf++) val[leaf] = 1;
for (int leaf = n+1+M; leaf <= (M<<1^1); leaf++) val[leaf] = 0;
for (int rt = M; rt >= 1; rt--) val[rt] = val[lc] + val[rc];
}

inline int update(int pos, int rt){
val[rt]--;
if (rt > M) return rt - M;
if (val[lc] >= pos) return update(pos, lc);
else return update(pos-val[lc], rc);
}
} T;

int main(){
//freopen("in.txt", "r", stdin);
int &mod = T.val[1];
for (LL k; ~scanf("%lld%lld\n", &n, &k);){
for (int i = 1; i <= n; i++) arr[i].read();
T.build(n);
ansPos = INF;
maxNum = 0;
dfs(0, 1, 1);

int pos = 0;
for (int i = 1; i <= ansPos; i++){
pos = T.update(k, 1);
//printf("k = %lld, pos = %d, mod = %d\n", k, pos, mod);
if (mod == 0) break;
if (arr[pos].val>0) k = (k-1 + arr[pos].val) % mod;
else k = ((k + arr[pos].val) % mod + mod) % mod;
if (k == 0) k = mod;
}
printf("%s %lld\n", arr[pos].name, maxNum);
}
return 0;
}