[tutorial:1091A]↵
[tutorial:1091B]↵
[tutorial:1091C]↵
[tutorial:1091D]↵
[tutorial:1091E]↵
[tutorial:1091F]↵
[tutorial:1091G]↵
[tutorial:1091H]↵
<spoiler summary="Code (by arsijo)">↵
```↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
int main(){↵
int a, b, c;↵
cin >> a >> b >> c;↵
cout << min(a + 2, min(b + 1, c)) * 3 - 3;↵
}↵
```↵
</spoiler>↵
↵
[tutorial:1091B]↵
↵
<spoiler summary="Code">↵
```↵
#include <vector>↵
#include <algorithm>↵
#include <iostream>↵
↵
using namespace std;↵
↵
typedef pair<int,int> pii;↵
↵
#define x first↵
#define y second↵
↵
int main() {↵
int N; cin >> N;↵
vector<pii> O(N), T(N);↵
for (int i = 0; i < N; i++) cin >> O[i].x >> O[i].y;↵
for (int i = 0; i < N; i++) cin >> T[i].x >> T[i].y;↵
sort(O.begin(),O.end());↵
sort(T.begin(),T.end());↵
reverse(T.begin(),T.end());↵
↵
vector<pii> Ans(N);↵
for (int i = 0; i < N; i++) Ans[i] = {O[i].x+T[i].x, O[i].y+T[i].y};↵
sort(Ans.begin(),Ans.end());↵
cout << Ans[0].x << ' ' << Ans[0].y << endl;↵
}↵
```↵
</spoiler>↵
↵
[tutorial:1091C]↵
↵
<spoiler summary="Code">↵
```↵
#include <iostream>↵
#include <vector>↵
#include <algorithm>↵
↵
using namespace std;↵
↵
typedef long long ll;↵
↵
int main() {↵
ll N; cin >> N;↵
vector<ll> ans;↵
↵
for (ll i = 1; i*i <= N; ++i) {↵
if (N%i==0) {↵
ans.push_back(N*(i-1)/2 + i);↵
if (i*i!=N) {↵
ans.push_back(N*(N/i-1)/2 + N/i);↵
}↵
}↵
}↵
sort(ans.begin(),ans.end());↵
↵
for (int i = 0; i < ans.size(); ++i) {↵
cout << ans[i] << " \n"[i==ans.size()-1];↵
}↵
↵
}↵
```↵
</spoiler>↵
↵
[tutorial:1091D]↵
↵
<spoiler summary="Code">↵
```↵
#include <iostream>↵
#include <vector>↵
↵
using namespace std;↵
↵
template <unsigned int N> class Field {↵
typedef unsigned int ui;↵
typedef unsigned long long ull;↵
inline ui pow(ui a, ui p){ui r=1,e=a;while(p){if(p&1){r=((ull)r*e)%N;}e=((ull)e*e)%N;p>>=1;}return r;}↵
inline ui inv(ui a){return pow(a,N-2);}↵
public:↵
inline Field(int x = 0) : v(x) {}↵
inline Field<N> pow(int p){return (*this)^p; }↵
inline Field<N> operator^(int p){return {(int)pow(v,(ui)p)};}↵
inline Field<N>&operator+=(const Field<N>&o) {if (v+o.v >= N) v += o.v - N; else v += o.v; return *this; }↵
inline Field<N>&operator-=(const Field<N>&o) {if (v<o.v) v -= o.v-N; else v-=o.v; return *this; }↵
inline Field<N>&operator*=(const Field<N>&o) {v=(ull)v*o.v % N; return *this; }↵
inline Field<N>&operator/=(const Field<N>&o) { return *this*=inv(o.v); }↵
inline Field<N> operator+(const Field<N>&o) const {Field<N>r{*this};return r+=o;}↵
inline Field<N> operator-(const Field<N>&o) const {Field<N>r{*this};return r-=o;}↵
inline Field<N> operator*(const Field<N>&o) const {Field<N>r{*this};return r*=o;}↵
inline Field<N> operator/(const Field<N>&o) const {Field<N>r{*this};return r/=o;}↵
inline Field<N> operator-() {if(v) return {(int)(N-v)}; else return {0};};↵
inline Field<N>& operator++() { ++v; if (v==N) v=0; return *this; }↵
inline Field<N> operator++(int) { Field<N>r{*this}; ++*this; return r; }↵
inline Field<N>& operator--() { --v; if (v==-1) v=N-1; return *this; }↵
inline Field<N> operator--(int) { Field<N>r{*this}; --*this; return r; }↵
inline bool operator==(const Field<N>&o) const { return o.v==v; }↵
inline bool operator!=(const Field<N>&o) const { return o.v!=v; }↵
inline explicit operator ui() const { return v; }↵
inline static vector<Field<N>>fact(int t){vector<Field<N>>F(t+1,1);for(int i=2;i<=t;++i){F[i]=F[i-1]*i;}return F;}↵
inline static vector<Field<N>>invfact(int t){vector<Field<N>>F(t+1,1);Field<N> X{1};for(int i=2;i<=t;++i){X=X*i;}F[t]=1/X;for(int i=t-1;i>=2;--i){F[i]=F[i+1]*(i+1);}return F;}↵
private: ui v;↵
};↵
template<unsigned int N>istream &operator>>(std::istream&is,Field<N>&f){unsigned int v;is>>v;f=v;return is;}↵
template<unsigned int N>ostream &operator<<(std::ostream&os,const Field<N>&f){return os<<(unsigned int)f;}↵
template<unsigned int N>Field<N> operator+(int i,const Field<N>&f){return Field<N>(i)+f;}↵
template<unsigned int N>Field<N> operator-(int i,const Field<N>&f){return Field<N>(i)-f;}↵
template<unsigned int N>Field<N> operator*(int i,const Field<N>&f){return Field<N>(i)*f;}↵
template<unsigned int N>Field<N> operator/(int i,const Field<N>&f){return Field<N>(i)/f;}↵
↵
typedef Field<998244353> FF;↵
↵
int main(int argc, char* argv[]) {↵
int n; cin >> n;↵
auto F = FF::fact(n);↵
auto I = FF::invfact(n);↵
FF ans = n * F[n];↵
for (int i = 1; i < n; ++i) ans -= F[n]*I[i];↵
cout << ans << endl;↵
}↵
```↵
</spoiler>↵
↵
[tutorial:1091E]↵
↵
<spoiler summary="Code">↵
```↵
#include <iostream>↵
#include <algorithm>↵
#include <vector>↵
using namespace std;↵
↵
#define MAXN 500000↵
↵
int N;↵
int A[MAXN];↵
long long sum;↵
↵
#define TOO_SMALL -1↵
#define OK 0↵
#define TOO_BIG 1↵
↵
int is_score(int value) {↵
vector<int> C(N+1,0);↵
for (int i = 0; i < N; ++i) ++C[A[i]];↵
++C[value];↵
↵
int less = 0;↵
long long left = 0, right = 0;↵
for (int k = 0, i = 0; k <= N; k++) {↵
int val = (i == k && (i == N || A[i] < value)) ? value : A[i++];↵
left += val;↵
--C[val];↵
right -= min(val, k);↵
less += C[k];↵
right += N-k-less;↵
if (left > right + (long long)(k+1)*k) {↵
return (i == k) ? TOO_BIG : TOO_SMALL;↵
}↵
}↵
return OK;↵
}↵
↵
int main(int,char**) {↵
ios_base::sync_with_stdio(false);↵
↵
scanf("%d", &N);↵
sum = 0;↵
for (int i = 0; i < N; i++) {↵
scanf("%d", A + i);↵
sum += A[i];↵
}↵
↵
sort(A,A+N,greater<int>());↵
int parity = sum & 1;↵
int lo = 0, hi = (N - parity) / 2, lores = -1;↵
while (lo <= hi) {↵
int mid = (lo + hi) / 2;↵
if (is_score(2*mid + parity) == TOO_SMALL) {↵
lo = mid + 1;↵
} else {↵
lores = mid;↵
hi = mid - 1;↵
}↵
}↵
↵
lo = lores; ↵
hi = (N - parity) / 2; ↵
int hires = -1;↵
while (lo <= hi) {↵
int mid = (lo + hi) / 2;↵
if (is_score(2*mid + parity) == TOO_BIG) {↵
hi = mid - 1;↵
} else {↵
hires = mid;↵
lo = mid + 1;↵
}↵
}↵
↵
if (lores == -1 || hires == -1) printf("-1\n"); ↵
else {↵
for (int i = lores; i <= hires; ++i) printf("%d ", 2*i+parity);↵
printf("\n");↵
}↵
}↵
```↵
</spoiler>↵
↵
[tutorial:1091F]↵
↵
<spoiler summary="Code">↵
```↵
#include <iostream>↵
#include <vector>↵
#include <string>↵
↵
typedef long long ll;↵
using namespace std;↵
↵
int main() {↵
int N; cin >> N;↵
vector<ll> L(N); ↵
for (ll &l: L) cin >> l;↵
string T; cin >> T;↵
bool hadWater = false;↵
ll time = 0, stamina = 0, twiceGrass = 0;↵
for (int i = 0; i < N; ++i) {↵
if (T[i] == 'L') {↵
time += L[i];↵
stamina -= L[i];↵
if (stamina < 0) {↵
/* not enough stamina, walk or swim "in place" to gain it */↵
time -= stamina * (hadWater ? 3 : 5);↵
stamina = 0;↵
}↵
} else if (T[i] == 'W') {↵
hadWater = true;↵
stamina += L[i];↵
time += 3 * L[i];↵
} else {↵
stamina += L[i];↵
time += 5 * L[i];↵
twiceGrass += 2*L[i]; ↵
}↵
/* no more than stamina/2 of walking can be converted to flying to save time,↵
* otherwise there would not be enough stamina at this point */↵
twiceGrass = min(twiceGrass, stamina);↵
}↵
↵
if (stamina > 0) {↵
// convert walking to flying↵
time -= (5-1) * twiceGrass/2;↵
↵
// convert swimming to flying↵
time -= (3-1) * (stamina - twiceGrass)/2;↵
}↵
↵
cout << time << endl;↵
}↵
```↵
</spoiler>↵
↵
[tutorial:1091G]↵
↵
<spoiler summary="Code (by winger)">↵
```↵
import random↵
↵
def isPrime(n):↵
"""↵
Miller-Rabin primality test.↵
↵
A return value of False means n is certainly not prime. A return value of↵
True means n is very likely a prime.↵
"""↵
if n!=int(n):↵
return False↵
n=int(n)↵
#Miller-Rabin test for prime↵
if n==0 or n==1 or n==4 or n==6 or n==8 or n==9:↵
return False↵
↵
if n==2 or n==3 or n==5 or n==7:↵
return True↵
s = 0↵
d = n-1↵
while d%2==0:↵
d>>=1↵
s+=1↵
assert(2**s * d == n-1)↵
↵
def trial_composite(a):↵
if pow(a, d, n) == 1:↵
return False↵
for i in range(s):↵
if pow(a, 2**i * d, n) == n-1:↵
return False↵
return True↵
↵
for i in range(20):#number of trials↵
a = random.randrange(2, n)↵
if trial_composite(a):↵
return False↵
↵
return True↵
↵
def gcd(x, y):↵
return x if y == 0 else gcd(y, x % y)↵
↵
n = int(input())↵
↵
divs = [n]↵
↵
def split(parts):↵
global divs↵
divs = [gcd(d, p) for d in divs for p in parts if gcd(d, p) != 1]↵
↵
while not all([isPrime(x) for x in divs]):↵
x = random.randint(0, n - 1)↵
g = gcd(n, x)↵
if gcd(n, x) != 1:↵
split([g, n // g])↵
continue↵
y = int(input('sqrt {}\n'.format(x * x % n)))↵
if x == y:↵
continue↵
a, b = abs(x - y), x + y↵
g = gcd(x, y)↵
split([a // g, b // g, g])↵
↵
print('!', len(divs), ' '.join(str(d) for d in sorted(divs)))↵
```↵
</spoiler>↵
↵
[tutorial:1091H]↵
↵
<spoiler summary="Code">↵
```↵
#include <vector>↵
#include <stack>↵
#include <iostream>↵
#include <algorithm>↵
#include <bitset>↵
using namespace std;↵
↵
typedef unsigned int ui;↵
typedef long long ll;↵
↵
struct Sieve : public std::vector<bool> {↵
// ~10ns * n↵
explicit Sieve(ui n) : vector<bool>(n+1, true), n(n) {↵
at(0) = false;↵
if (n!=0) at(1) = false;↵
for (ui i = 2; i*i <= n; ++i) {↵
if (at(i)) for (int j = i*i; j <= n; j+=i) (*this)[j] = false;↵
}↵
}↵
↵
vector<int> primes() const {↵
vector<int> ans;↵
for (int i=2; i<=n; ++i) if (at(i)) ans.push_back(i);↵
return ans;↵
}↵
↵
private:↵
int n;↵
};↵
↵
constexpr int M = 2e5;↵
auto P = Sieve{M}.primes();↵
↵
int main() {↵
ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);↵
↵
vector<int> G(M, 0);↵
int Q = P.size();↵
for (int i = 0; i < Q; ++i) {↵
for (int j = i; j < Q; ++j) {↵
if (ll(P[i])*P[j] >= M) break;↵
P.push_back(P[i]*P[j]);↵
}↵
}↵
↵
bitset<M> PB;↵
for (int p : P) PB[p] = true;↵
↵
int N, F; cin >> N >> F;↵
PB[F] = false;↵
↵
vector<bitset<M>> W(100);↵
W[0] = PB;↵
for (int i = 1; i < M; ++i) {↵
while (W[G[i]][i]) G[i]++;↵
W[G[i]] |= PB << i;↵
}↵
cerr << *max_element(G.begin(),G.end()) << endl;↵
↵
int g = 0;↵
for (int i = 0; i < N; i++) {↵
int r,w,b;↵
cin >> r >> w >> b;↵
g ^= G[w-r-1];↵
g ^= G[b-w-1];↵
}↵
if (g == 0) {↵
cout << "Bob\nAlice\n";↵
} else {↵
cout << "Alice\nBob\n";↵
}↵
}↵
```↵
</spoiler>↵
↵
[tutorial:1091C]↵
[tutorial:1091D]↵
[tutorial:1091E]↵
[tutorial:1091F]↵
[tutorial:1091G]↵
[tutorial:1091H]
<spoiler summary="Code (by arsijo)">↵
```↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
int main(){↵
int a, b, c;↵
cin >> a >> b >> c;↵
cout << min(a + 2, min(b + 1, c)) * 3 - 3;↵
}↵
```↵
</spoiler>↵
↵
[tutorial:1091B]↵
↵
<spoiler summary="Code">↵
```↵
#include <vector>↵
#include <algorithm>↵
#include <iostream>↵
↵
using namespace std;↵
↵
typedef pair<int,int> pii;↵
↵
#define x first↵
#define y second↵
↵
int main() {↵
int N; cin >> N;↵
vector<pii> O(N), T(N);↵
for (int i = 0; i < N; i++) cin >> O[i].x >> O[i].y;↵
for (int i = 0; i < N; i++) cin >> T[i].x >> T[i].y;↵
sort(O.begin(),O.end());↵
sort(T.begin(),T.end());↵
reverse(T.begin(),T.end());↵
↵
vector<pii> Ans(N);↵
for (int i = 0; i < N; i++) Ans[i] = {O[i].x+T[i].x, O[i].y+T[i].y};↵
sort(Ans.begin(),Ans.end());↵
cout << Ans[0].x << ' ' << Ans[0].y << endl;↵
}↵
```↵
</spoiler>↵
↵
[tutorial:1091C]↵
↵
<spoiler summary="Code">↵
```↵
#include <iostream>↵
#include <vector>↵
#include <algorithm>↵
↵
using namespace std;↵
↵
typedef long long ll;↵
↵
int main() {↵
ll N; cin >> N;↵
vector<ll> ans;↵
↵
for (ll i = 1; i*i <= N; ++i) {↵
if (N%i==0) {↵
ans.push_back(N*(i-1)/2 + i);↵
if (i*i!=N) {↵
ans.push_back(N*(N/i-1)/2 + N/i);↵
}↵
}↵
}↵
sort(ans.begin(),ans.end());↵
↵
for (int i = 0; i < ans.size(); ++i) {↵
cout << ans[i] << " \n"[i==ans.size()-1];↵
}↵
↵
}↵
```↵
</spoiler>↵
↵
[tutorial:1091D]↵
↵
<spoiler summary="Code">↵
```↵
#include <iostream>↵
#include <vector>↵
↵
using namespace std;↵
↵
template <unsigned int N> class Field {↵
typedef unsigned int ui;↵
typedef unsigned long long ull;↵
inline ui pow(ui a, ui p){ui r=1,e=a;while(p){if(p&1){r=((ull)r*e)%N;}e=((ull)e*e)%N;p>>=1;}return r;}↵
inline ui inv(ui a){return pow(a,N-2);}↵
public:↵
inline Field(int x = 0) : v(x) {}↵
inline Field<N> pow(int p){return (*this)^p; }↵
inline Field<N> operator^(int p){return {(int)pow(v,(ui)p)};}↵
inline Field<N>&operator+=(const Field<N>&o) {if (v+o.v >= N) v += o.v - N; else v += o.v; return *this; }↵
inline Field<N>&operator-=(const Field<N>&o) {if (v<o.v) v -= o.v-N; else v-=o.v; return *this; }↵
inline Field<N>&operator*=(const Field<N>&o) {v=(ull)v*o.v % N; return *this; }↵
inline Field<N>&operator/=(const Field<N>&o) { return *this*=inv(o.v); }↵
inline Field<N> operator+(const Field<N>&o) const {Field<N>r{*this};return r+=o;}↵
inline Field<N> operator-(const Field<N>&o) const {Field<N>r{*this};return r-=o;}↵
inline Field<N> operator*(const Field<N>&o) const {Field<N>r{*this};return r*=o;}↵
inline Field<N> operator/(const Field<N>&o) const {Field<N>r{*this};return r/=o;}↵
inline Field<N> operator-() {if(v) return {(int)(N-v)}; else return {0};};↵
inline Field<N>& operator++() { ++v; if (v==N) v=0; return *this; }↵
inline Field<N> operator++(int) { Field<N>r{*this}; ++*this; return r; }↵
inline Field<N>& operator--() { --v; if (v==-1) v=N-1; return *this; }↵
inline Field<N> operator--(int) { Field<N>r{*this}; --*this; return r; }↵
inline bool operator==(const Field<N>&o) const { return o.v==v; }↵
inline bool operator!=(const Field<N>&o) const { return o.v!=v; }↵
inline explicit operator ui() const { return v; }↵
inline static vector<Field<N>>fact(int t){vector<Field<N>>F(t+1,1);for(int i=2;i<=t;++i){F[i]=F[i-1]*i;}return F;}↵
inline static vector<Field<N>>invfact(int t){vector<Field<N>>F(t+1,1);Field<N> X{1};for(int i=2;i<=t;++i){X=X*i;}F[t]=1/X;for(int i=t-1;i>=2;--i){F[i]=F[i+1]*(i+1);}return F;}↵
private: ui v;↵
};↵
template<unsigned int N>istream &operator>>(std::istream&is,Field<N>&f){unsigned int v;is>>v;f=v;return is;}↵
template<unsigned int N>ostream &operator<<(std::ostream&os,const Field<N>&f){return os<<(unsigned int)f;}↵
template<unsigned int N>Field<N> operator+(int i,const Field<N>&f){return Field<N>(i)+f;}↵
template<unsigned int N>Field<N> operator-(int i,const Field<N>&f){return Field<N>(i)-f;}↵
template<unsigned int N>Field<N> operator*(int i,const Field<N>&f){return Field<N>(i)*f;}↵
template<unsigned int N>Field<N> operator/(int i,const Field<N>&f){return Field<N>(i)/f;}↵
↵
typedef Field<998244353> FF;↵
↵
int main(int argc, char* argv[]) {↵
int n; cin >> n;↵
auto F = FF::fact(n);↵
auto I = FF::invfact(n);↵
FF ans = n * F[n];↵
for (int i = 1; i < n; ++i) ans -= F[n]*I[i];↵
cout << ans << endl;↵
}↵
```↵
</spoiler>↵
↵
[tutorial:1091E]↵
↵
<spoiler summary="Code">↵
```↵
#include <iostream>↵
#include <algorithm>↵
#include <vector>↵
using namespace std;↵
↵
#define MAXN 500000↵
↵
int N;↵
int A[MAXN];↵
long long sum;↵
↵
#define TOO_SMALL -1↵
#define OK 0↵
#define TOO_BIG 1↵
↵
int is_score(int value) {↵
vector<int> C(N+1,0);↵
for (int i = 0; i < N; ++i) ++C[A[i]];↵
++C[value];↵
↵
int less = 0;↵
long long left = 0, right = 0;↵
for (int k = 0, i = 0; k <= N; k++) {↵
int val = (i == k && (i == N || A[i] < value)) ? value : A[i++];↵
left += val;↵
--C[val];↵
right -= min(val, k);↵
less += C[k];↵
right += N-k-less;↵
if (left > right + (long long)(k+1)*k) {↵
return (i == k) ? TOO_BIG : TOO_SMALL;↵
}↵
}↵
return OK;↵
}↵
↵
int main(int,char**) {↵
ios_base::sync_with_stdio(false);↵
↵
scanf("%d", &N);↵
sum = 0;↵
for (int i = 0; i < N; i++) {↵
scanf("%d", A + i);↵
sum += A[i];↵
}↵
↵
sort(A,A+N,greater<int>());↵
int parity = sum & 1;↵
int lo = 0, hi = (N - parity) / 2, lores = -1;↵
while (lo <= hi) {↵
int mid = (lo + hi) / 2;↵
if (is_score(2*mid + parity) == TOO_SMALL) {↵
lo = mid + 1;↵
} else {↵
lores = mid;↵
hi = mid - 1;↵
}↵
}↵
↵
lo = lores; ↵
hi = (N - parity) / 2; ↵
int hires = -1;↵
while (lo <= hi) {↵
int mid = (lo + hi) / 2;↵
if (is_score(2*mid + parity) == TOO_BIG) {↵
hi = mid - 1;↵
} else {↵
hires = mid;↵
lo = mid + 1;↵
}↵
}↵
↵
if (lores == -1 || hires == -1) printf("-1\n"); ↵
else {↵
for (int i = lores; i <= hires; ++i) printf("%d ", 2*i+parity);↵
printf("\n");↵
}↵
}↵
```↵
</spoiler>↵
↵
[tutorial:1091F]↵
↵
<spoiler summary="Code">↵
```↵
#include <iostream>↵
#include <vector>↵
#include <string>↵
↵
typedef long long ll;↵
using namespace std;↵
↵
int main() {↵
int N; cin >> N;↵
vector<ll> L(N); ↵
for (ll &l: L) cin >> l;↵
string T; cin >> T;↵
bool hadWater = false;↵
ll time = 0, stamina = 0, twiceGrass = 0;↵
for (int i = 0; i < N; ++i) {↵
if (T[i] == 'L') {↵
time += L[i];↵
stamina -= L[i];↵
if (stamina < 0) {↵
/* not enough stamina, walk or swim "in place" to gain it */↵
time -= stamina * (hadWater ? 3 : 5);↵
stamina = 0;↵
}↵
} else if (T[i] == 'W') {↵
hadWater = true;↵
stamina += L[i];↵
time += 3 * L[i];↵
} else {↵
stamina += L[i];↵
time += 5 * L[i];↵
twiceGrass += 2*L[i]; ↵
}↵
/* no more than stamina/2 of walking can be converted to flying to save time,↵
* otherwise there would not be enough stamina at this point */↵
twiceGrass = min(twiceGrass, stamina);↵
}↵
↵
if (stamina > 0) {↵
// convert walking to flying↵
time -= (5-1) * twiceGrass/2;↵
↵
// convert swimming to flying↵
time -= (3-1) * (stamina - twiceGrass)/2;↵
}↵
↵
cout << time << endl;↵
}↵
```↵
</spoiler>↵
↵
[tutorial:1091G]↵
↵
<spoiler summary="Code (by winger)">↵
```↵
import random↵
↵
def isPrime(n):↵
"""↵
Miller-Rabin primality test.↵
↵
A return value of False means n is certainly not prime. A return value of↵
True means n is very likely a prime.↵
"""↵
if n!=int(n):↵
return False↵
n=int(n)↵
#Miller-Rabin test for prime↵
if n==0 or n==1 or n==4 or n==6 or n==8 or n==9:↵
return False↵
↵
if n==2 or n==3 or n==5 or n==7:↵
return True↵
s = 0↵
d = n-1↵
while d%2==0:↵
d>>=1↵
s+=1↵
assert(2**s * d == n-1)↵
↵
def trial_composite(a):↵
if pow(a, d, n) == 1:↵
return False↵
for i in range(s):↵
if pow(a, 2**i * d, n) == n-1:↵
return False↵
return True↵
↵
for i in range(20):#number of trials↵
a = random.randrange(2, n)↵
if trial_composite(a):↵
return False↵
↵
return True↵
↵
def gcd(x, y):↵
return x if y == 0 else gcd(y, x % y)↵
↵
n = int(input())↵
↵
divs = [n]↵
↵
def split(parts):↵
global divs↵
divs = [gcd(d, p) for d in divs for p in parts if gcd(d, p) != 1]↵
↵
while not all([isPrime(x) for x in divs]):↵
x = random.randint(0, n - 1)↵
g = gcd(n, x)↵
if gcd(n, x) != 1:↵
split([g, n // g])↵
continue↵
y = int(input('sqrt {}\n'.format(x * x % n)))↵
if x == y:↵
continue↵
a, b = abs(x - y), x + y↵
g = gcd(x, y)↵
split([a // g, b // g, g])↵
↵
print('!', len(divs), ' '.join(str(d) for d in sorted(divs)))↵
```↵
</spoiler>↵
↵
[tutorial:1091H]↵
↵
<spoiler summary="Code">↵
```↵
#include <vector>↵
#include <stack>↵
#include <iostream>↵
#include <algorithm>↵
#include <bitset>↵
using namespace std;↵
↵
typedef unsigned int ui;↵
typedef long long ll;↵
↵
struct Sieve : public std::vector<bool> {↵
// ~10ns * n↵
explicit Sieve(ui n) : vector<bool>(n+1, true), n(n) {↵
at(0) = false;↵
if (n!=0) at(1) = false;↵
for (ui i = 2; i*i <= n; ++i) {↵
if (at(i)) for (int j = i*i; j <= n; j+=i) (*this)[j] = false;↵
}↵
}↵
↵
vector<int> primes() const {↵
vector<int> ans;↵
for (int i=2; i<=n; ++i) if (at(i)) ans.push_back(i);↵
return ans;↵
}↵
↵
private:↵
int n;↵
};↵
↵
constexpr int M = 2e5;↵
auto P = Sieve{M}.primes();↵
↵
int main() {↵
ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);↵
↵
vector<int> G(M, 0);↵
int Q = P.size();↵
for (int i = 0; i < Q; ++i) {↵
for (int j = i; j < Q; ++j) {↵
if (ll(P[i])*P[j] >= M) break;↵
P.push_back(P[i]*P[j]);↵
}↵
}↵
↵
bitset<M> PB;↵
for (int p : P) PB[p] = true;↵
↵
int N, F; cin >> N >> F;↵
PB[F] = false;↵
↵
vector<bitset<M>> W(100);↵
W[0] = PB;↵
for (int i = 1; i < M; ++i) {↵
while (W[G[i]][i]) G[i]++;↵
W[G[i]] |= PB << i;↵
}↵
cerr << *max_element(G.begin(),G.end()) << endl;↵
↵
int g = 0;↵
for (int i = 0; i < N; i++) {↵
int r,w,b;↵
cin >> r >> w >> b;↵
g ^= G[w-r-1];↵
g ^= G[b-w-1];↵
}↵
if (g == 0) {↵
cout << "Bob\nAlice\n";↵
} else {↵
cout << "Alice\nBob\n";↵
}↵
}↵
```↵
</spoiler>↵
↵
