2019 Multi-University Training Contest 3
2019-07-29 / Luo Jinrong   

进度

A B C D E F G H I J K

1006. Fansblog

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#include<bits/stdc++.h>
#define FIN freopen("./1006.in","r",stdin)
#define debug(x) cout<<#x"=["<<x<<"]"<<endl
using namespace std;
typedef long long ll;
const ll maxn(1e5+5);
const double pi=acos(-1);
ll T;
__int128 ans,p,q;
void _print(__int128 x)
{
if(x > 9) _print(x/10);
putchar(x%10 + '0');
}
void scan(__int128 &x)//输入
{
x = 0;
int f = 1;
char ch;
if((ch = getchar()) == '-') f = -f;
else x = x*10 + ch-'0';
while((ch = getchar()) >= '0' && ch <= '9')
x = x*10 + ch-'0';
x *= f;
}
void print(__int128 x)
{
if(x<0){
x=-x;
putchar('-');
}
if(!x)
{
puts("0");
return ;
}
string ret="";
while(x)
{
ret+=x%10+'0';
x/=10;
}
reverse(ret.begin(),ret.end());
cout<<ret<<endl;
}
//ll igcdex(ll a,ll b){
// ll x_sign,y_sign,x=1,y=0,r=0,s=1,c,q;
// if(a==0&&b==0){
// return 0;
// }
// if(a==0){
// return 0;
// }
// if(b==0){
// return a/abs(a);
// }
// if(a<0){
// a=-a,x_sign=-1;
// }else{
// x_sign=1;
// }
// if(b<0){
// b=-b,y_sign=-1;
// }else{
// y_sign=1;
// }
// while(b){
// c=a%b,q=a/b;
// a=b,b=c,r=x-q*r,s=y-q*s,x=r,y=s;
// }
// return x*x_sign;
//}
ll exgcd(__int128 a,__int128 b,__int128 &x,__int128 &y){
if(!b){
y=0;x=1;return a;
}
ll d=exgcd(b,a%b,y,x);y-=a/b*x;return d;
}
int main(){
#ifndef ONLINE_JUDGE
FIN;
#endif
// ios_base::sync_with_stdio(false);
// cin.tie(0);
// cout.tie(0);
cin>>T;
getchar();
while(T--){
scan(q);
for(ll i=q-2;i>=2;i-=2){
ll flag=1;
for(ll j=2;j<sqrt(i)+1;j++){
if(i%j==0){
flag=0;
break;
}
}
if(flag){
p=i;
break;
}
}
ans=q-1;
for(ll i=p+1;i<q;i++){
__int128 x,y;
exgcd(i,q,x,y);
ans=(ans*(x%q+q))%q;
//ans=(ans*igcdex(i,q))%q;
}
print(ans);
}
}
/*
#include <bits/stdc++.h>
using namespace std;

void scan(__int128 &x)//输入
{
x = 0;
int f = 1;
char ch;
if((ch = getchar()) == '-') f = -f;
else x = x*10 + ch-'0';
while((ch = getchar()) >= '0' && ch <= '9')
x = x*10 + ch-'0';
x *= f;
}
void _print(__int128 x)
{
if(x > 9) _print(x/10);
putchar(x%10 + '0');
}
void print(__int128 x)//输出
{
if(x < 0)
{
x = -x;
putchar('-');
}
_print(x);
}

int main()
{
__int128 a, b;
scan(a); scan(b);
print(a + b);
return 0;
}
*/

1007. Find the answer

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MAXN maxn
#define per(a,b,c) for(int a=b;a<c;++a)
#define rep(a,b,c) for(int a=c-1;a>=b;--a)
int T,n,m;
const int MAXN(500010);
ll b[MAXN], summ[MAXN << 2], ptnm[MAXN << 2];
ll outt[MAXN], tmpp;

struct nd{
ll val, no;
}a[MAXN];

//(1)更新结点信息
void PushUp(int rt) {
summ[rt] = summ[rt << 1] + summ[rt << 1 | 1];
ptnm[rt] = ptnm[rt << 1] + ptnm[rt << 1 | 1];
}

//(2)建树
void Build(int l, int r, int rt) {
if (l == r) {
summ[rt] = a[l].val;
ptnm[rt] = 1;
return;
}
int mid = (l + r) >> 1;
Build(l, mid, rt << 1);
Build(mid + 1, r, rt << 1 | 1);
PushUp(rt);
}

//(4)点更新
void Add(int L, ll C, int l, int r, int rt) {
if (l == r) {
summ[rt] -= C;
ptnm[rt]--;
return;
}
int mid = (l + r) >> 1;
//PushDown(rt,mid-l+1,r-mid); 若既有点更新又有区间更新,需要这句话
if (L <= mid) {
summ[rt] -= C;
ptnm[rt]--;
Add(L, C, l, mid, rt << 1);
} else {
summ[rt] -= C;
ptnm[rt]--;
Add(L, C, mid + 1, r, rt << 1 | 1); }
}

//(6)区间查询
int Query(ll C, int l, int r, int rt) {
if(C<=0) return 0;
if (l==r)
return 1;
int mid = (l + r) >> 1, ls=(rt<<1), rs=(rt<<1|1);
if (summ[ls] > C) { return Query(C, l, mid, ls); }
else { return ptnm[ls]+Query(C-summ[ls], mid + 1, r, rs); }
}

int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>T;
while(T--){
cin >> n >> m;
tmpp = 0;
per(i, 1, n+1) {
cin >> a[i].val;
a[i].no=i;
tmpp+=a[i].val;
}
sort(a+1, a+1+n, [](const nd& a, const nd& b) {return a.val>b.val;});
per(i, 1, n+1) {
b[a[i].no]=i;
}
tmpp-=m;
Build(1, n, 1);
rep(i, 1, n+1) {
Add(b[i], a[b[i]].val, 1, n, 1);
outt[i] = Query(tmpp, 1, n, 1);
tmpp -= a[b[i]].val;
}
per(i, 1, n+1) {
cout << outt[i] << " ";
}
cout << "\n";
}
return 0;
}

return 0;


本文链接:
https://luojinrong.github.io/2019/07/29/2019-Multi-University-Training-Contest-3/